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

Solution 1:

$$\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}$$

Solution 2:

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.

Solution 3:

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