How to prove that $\frac{(mn)!}{m!(n!)^m}$ is an integer?

$\forall m,n\in\mathbb Z$ , $m\ge1$ and $n\ge1$ how to prove that $$\frac{(mn)!}{m!(n!)^m}$$ is an integer?

Thanks in advance.

Solution 1:

We have a group of $mn$ people, and want to divide them into $m$ teams of $n$ people each. Your expression is precisely the number of ways to do it. Since the expression counts something, it must always yield an integer.

To count the number of ways to divide the group into $m$ teams, we first count the number of ways to divide them into teams that will wear uniform colours $C_1,C_2,\dots,C_m$.

Line up the people. There are $(mn)!$ ways to do this. Take the first group of $n$, assign it uniforms $C_1$, and so on. This overcounts the number of ways to divide into uniformed teams, since any permutation of the first $n$ people, followed by any permutation of the next $n$, and so on, yields the same subdivision into uniformed teams. It follows that there are $\dfrac{(mn)!}{(n!)^m}$ divisions into uniformed teams.

Any permutation of the uniform colours yields the same division into uniformless teams. So the number of ways to divide our group into teams is $\dfrac{1}{m!}\dfrac{(mn)!}{(n!)^m}$

Solution 2:

Note that $\binom{kn}{n}$ must contain a multiple of $k$ therefore $\frac{1}{k}\binom{kn}{n}$ is always an integer.

$$\frac{1}{m!}\cdot\frac{(mn)!}{(n!)^m}=\frac{1}{1}\binom{n}{n}\frac{1}{2}\binom{2n}{n}\cdots\frac{1}{m}\binom{nm}{n}$$

All of these terms are integers!