# 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.

#### Solutions Collecting From Web of "Show that for any positive integer n, $(3n)!/(3!)^n$ is an integer."

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.

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

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?

Hint: $3! \mid (3k-2)(3k-1)3k$ for $k=1,2,\ldots n$.

In the product $(3n)! = 3n \times (3n – 1) \times \dots \times 2 \times 1$, precisely $n$ terms are divisible by $3$, so $3^n\ |\ (3n)!$ and there are $\lfloor\frac{3n}{2}\rfloor \geq n$ terms divisible by $2$, so $2^n\ |\ (3n)!$. As $2^n$ and $3^n$ are coprime, $3^n2^n\ | (3n)!$. Now note that $(3!)^n = (3\times 2\times 1)^n = 3^n\times 2^n \times 1^n = 3^n2^n$.