Prove that $(n^2)!$ is divisible by $(n!)^{n+1}$ for all positive integers $n$.
$\underline{SOLUTION}$: The number of ways of forming $n$ distinct $n$-member committees out of $n^2$ people is the multinomial coefficient $$\frac{(n^2)!}{(n!)^n}$$
To count the number of ways of forming $n$ indistinct $n$-member committees out of $n^2$ people,we must divide this multinomial coefficient by $n!$, obtaining
$$\frac{(n^2)!}{(n!)^{n+1}}$$
Which must be an integer.
I've stared at this problem for a while now and I can't seem to see why the first expression is equal to the number of ways to form $n$ distinct $n$-member committees out of $n^2$ people. If anyone could explain why this is true, it would be greatly appreciated, thanks!
There are $\binom{n^2}{n}$ ways to pick the first group.
Then $\binom{n^2-n}{n}$ for the next, $\binom{n^2-2n}{n}$ after that, and so on.
Now by the combination's definition, we have
$\binom{n^2}{n}\binom{n^2-n}{n}\dots\binom{n}{n}=\frac{(n^2)!}{n!(n^2-n)!}\frac{(n^2-n)!}{n!(n^2-2n)!}\dots\frac{n!}{n!0!}=\frac{(n^2)!}{(n!)^n0!}$ since all of the numerators besides $(n^2)!$ cancel out with a factorial in the denominator.