How does one prove that $6$ divides ${(3n)!}/{(n!)^3}$? How does one prove that $6$ divides the multinomial coefficient $\displaystyle \frac{(3n)!}{\;(n!)^3}$?
 A: HINT: You have a deck of $3n$ cards numbered from $1$ through $3n$. You divide it into three hands of $n$ cards each. You have boxes labelled $A$, $B$, and $C$, and you put one hand into each box. There are $3!=6$ ways to decide which hand goes into which box, so if $h$ is the number of ways to split the deck into hands, there are $6h$ ways to split it into hands and put one hand into each box. What does $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$$ count in this model?
A: $\displaystyle
\frac{(3n)!}{\;(n!)^3} = 3n\frac{(3n-1)\cdots(2n)}{n!} \, \frac{(2n-1)\cdots n}{n!} \, \frac{(n-1)\cdots 1}{n!} =  3 {3n-1 \choose n} {2n-1 \choose n} 
$
$\displaystyle
\frac{(3n)!}{\;(n!)^3} = \frac{(3n)\cdots(2n+1)}{n!} \, 2n \, \frac{(2n-1)\cdots n}{n!} \, \frac{(n-1)\cdots 1}{n!} =  2 {3n \choose n} {2n-1 \choose n} 
$
So
$\displaystyle
\frac{(3n)!}{\;(n!)^3}$ is a multiple of $2$ and of $3$, hence a multiple of $6$.
Here is a simpler solution:
$\displaystyle
\frac{(3n)!}{\;(n!)^3} = {3n \choose n} {2n \choose n} = \frac{3n}{n}{3n-1 \choose n-1} \frac{2n}{n} {2n-1 \choose n-1} = 6 {3n-1 \choose n-1} {2n-1 \choose n-1}
$
This solution can be generalized to prove that $\displaystyle
\frac{(kn)!}{\;(n!)^k}$ is a multiple of $k!$.
A: $\binom{3n}{n,n,n}$ is the number of arrangements of $n$ A's, $n$ B's, and $n$ C's. In exactly one-sixth of them, the letters A, B, and C make their first appearances in the order A, B, C.
