Show that for any positive integer n, $(3n)!/(3!)^n$ is an integer.

This is also a question on my exam paper that i proved by using mathematical induction. However, my tutor tells me that it can be proved without using mathematical induction. I really want to know how to deal with in another way.

Show that for any positive integer n, $(3n)!/(3!)^n$ is an integer.

Solution 1:

Hint: $$ \begin{align} &\binom{3n}{3}\binom{3n-3}{3}\binom{3n-6}{3}\cdots\binom{6}{3}\binom{3}{3}\\ &=\frac{(3n)!}{\color{#C00000}{(3n-3)!}3!}\frac{\color{#C00000}{(3n-3)!}}{\color{#00A000}{(3n-6)!}3!}\frac{\color{#00A000}{(3n-6)!}}{\color{#A0A0A0}{(3n-9)!}3!} \cdots\frac{\color{#A0A0A0}{6!}}{\color{#0000FF}{3!}3!}\frac{\color{#0000FF}{3!}}{0!3!}\\ &=\frac{(3n)!}{(3!)^n} \end{align} $$ Only the solid black terms don't disappear.

Solution 2:

Hint: How many ways are there to form $n$ triples out of the first $3n$ positive integers?

Solution 3:

Count how many even numbers there are up to 3n. You should get at least n. similarly how multiples of 3 do you get? That means that $2^n$ and $3^n$ divide your number. This implies that $6^n$ divides your number. Why?