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!$. 

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.
