Prove $\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$ is always divisible by $6$ when $n$ is an integer. 
Prove $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!}$$ is always divisible by $6$ when $n$ is an integer. 

I have done a similar proof that $\binom{2n}{n}$ is divisible by $2$ by showing that $$\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n-1}$$ but I am at a loss for how to translate this to divisible by $6$. Another way to do this proof would be to show that when you shoot an $n$-element subset from $2n$ you can always match it with another subset (namely the $n$-elements that were not chosen). Again, no idea how to translate this to $6!$. 
 A: $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!} = \binom{3n}{n}\binom{2n}{n}$$
$$\binom{3n}{n} = \binom{3n -1}{n-1} +\binom{3n-1}{n} = \frac{(3n - 1)!}{(n-1)!(3n -1 -(n-1))!} + \frac{(3n - 1)!}{n! ((3n -1 -n)!}$$
$$=\frac{(3n-1)!)}{(n-1)!(2n-1)!}(\frac{1}{2n} + \frac{1}{n})$$
$$=\frac{(3n-1)!)}{(n-1)!(2n-1)!} \frac{3}{2n}$$
$$=\frac{(3n-1)!)}{(n-1)!(2n)!} * 3$$
$$=3\binom{3n -1}{n-1}$$
It has been already proved that
$$\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n-1}$$
Combining both
$$\binom{3n}{n,n,n} = \binom{3n}{n}\binom{2n}{n} = 6\binom{3n -1}{n-1}\binom{2n-1}{n-1}$$
A: Just count in how many ways you can partition a set of $3n$ elements into three sets of $n$ elements ignoring order.
If we consider the order, we get $\binom{3n}{n,n,n}$ ordered partitions. Each unordered partition is counted exactly $3!$ times (do you see why?), so the number of unordered partitions is exactly
$$\frac{1}{3!}\binom{3n}{n,n,n}$$
and it is necessarily an integer.
A: Notice that $$\binom{3n}{n,n,n}=\frac{(3n)!}{n!n!n!} = \binom{3n}{n}\binom{2n}{n}.$$ We have shown that $\binom{2n}{n}$ is divisible by 2. Now, all we must do is show that $\binom{3n}{n}$ is divisible by 3. You know that $\binom{3n}{n}$ is the number of n-element subsets of a 3n-element set (or, the number of ways to choose n objects among 3n distinct objects), which is always an integer. Note that $$\binom{3n}{n} = \frac{(3n)!}{(n!)(2n)!} = \frac{(3)(n)(3n - 1)!}{(n)(n-1)!(2n)!} = \frac{(3)(3n - 1)!}{(n-1)!(2n)!} = (3)\frac{(3n - 1)!}{(n-1)!(2n)!} = (3)\binom{3n-1}{n-1},$$ which is an integer and is divisible by 3.
By Peter's suggestion, you can generalize to say that for all integers k, $$\binom{kn}{n_{1},n_{2}, ... , n_{k}} = \binom{kn}{n}\binom{(k-1)n}{n}...\binom{(k-k+1)n}{n}$$ and $$\binom{kn}{n} = \frac{(kn!)}{n!(kn-n)!} = \frac{(kn)(kn-1)!}{(n)(n-1)!(kn-n)!} = k\binom{kn-1}{n-1}, $$ and use induction to prove that $$\binom{kn}{n_{1},n_{2}, ... , n_{k}}$$ is divisible by $k!.$
A: NOTE: This proof assumes $n-2 \geq 0$. The proof is trivial for $n=0$ and $n=1$.
By Pascal's Identity, we have the following:
$${3n \choose n, n, n}={3n-1 \choose n-1, n, n}+{3n-1 \choose n, n-1, n}+{3n-1 \choose n, n, n-1}=3{3n-1 \choose n-1, n, n}$$
Use Pascal's Identity on the new binomial coefficient:
$${3n-1 \choose n-1, n, n}={3n-2 \choose n-2, n, n}+{3n-2 \choose n-1, n-1, n}+{3n-2 \choose n-1, n, n-1}={3n-2 \choose n-2, n, n}+2{3n-2 \choose n-1, n-1, n}$$
In order to prove ${3n-2 \choose n-2, n, n}$ is divisible by $2$, we will now prove that ${2n+a \choose a, n, n}$ is divisible by $2$ by induction.
Base Case $a=0$:
$${2n \choose 0, n, n}={2n \choose n}$$
This is divisible by $2$ by your proof.
Induction Case:
$${2n+a \choose a, n, n}={2n+a-1 \choose a-1, n, n}+{2n+a-1 \choose a, n-1, n}+{2n+a-1 \choose a, n, n-1}={2n+a-1 \choose a-1, n, n}+2{2n+a-1 \choose a, n-1, n}$$
The former addend in this sum is divisible by $2$ by our induction hypothesis and the latter addend is obviously divisible by $2$, so the whole sum is divisible by $2$.
Thus, from this, we know that ${3n-2 \choose n-2, n, n}$ is divisible by $2$. Go back to our second sum:
$${3n-1 \choose n-1, n, n}={3n-2 \choose n-2, n, n}+2{3n-2 \choose n-1, n-1, n}$$
The former addend in this sum is divisible by $2$ by our lemma and the latter addend is obviously divisible by $2$, so the whole sum is divisible by $2$.
Now, go back to our original equation:
$${3n \choose n, n, n}=3{3n-1 \choose n-1, n, n}$$
A multiple of $2$ times $3$ is obviously divisible by $6$, concluding the proof.
