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

Question

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

Answer 1

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!

Answer 2

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

Answer 3

OK, since explicit solutions have been given, I will give the group-theoretic approach explicitly. The symmetric group $S_{nm}$ has a subgroup $S_{n} \wr S_{m}.$ This is a semidirect product of a base group $B$ with the symmetric group $S_{m}.$ The base group $B$ is itself a direct product of $m$ copies of $S_{n},$ and these factors are permuted around by the $S_{m}$ which acts on $B.$ The group $S_{n} \wr S_{m}$ therefore has order $m!(n!)^{m},$ which divides $(mn)!$ by Lagrange's theorem.

Answer 4

Divide the expression $(mn)!$ into m groups each group consisting of the nos. $\{(kn+1)(kn+2).....((k+1)n)\}$, here k runs from $0$ to $m-1$

So we have ,$\displaystyle (mn)!=\prod_{k=0}^{m-1}(kn+1)(kn+2).....((k+1)n)$

In each group first $n-1$ nos is divisible by $(n-1)!$ as we have m groups so the total product is divisible by $((n-1)!)^m$ (Using the fact that product of $k$ consecutive nos is divisible by $k!$)

Product of the last nos. of the group is $\displaystyle \prod_{k=0}^{m-1}(k+1)n=m!.n^m$

So the whole product is divisible by $((n-1)!)^m.m!.n^m=m!(n!)^m$

Hence proving the fact that $\displaystyle \frac{(mn)!}{m!(n!)^m}$ is an integer.

Answer 5

Use telescopy: $\rm\:f(0),\ f(k+1)/f(k)\in \Bbb Z\ \Rightarrow\: f(m)\in \Bbb Z\ $ since

$$\rm f(0)\ \ \prod_{k\:=\:0}^{m-1}\ \frac{f(k+1)}{f(k)}\ \ = \ \ \ \color{red}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{red}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}}\ \ \cdots\ \ \frac{\color{brown}{\rlap{----}f(m-1)}}{\phantom{\rlap{--}f(m-2)}}\frac{f(m)}{\color{brown}{\rlap{----}f(m-1)}}\ =\ \ f(m) $$

Indeed, one quickly verifies $\displaystyle\rm\,\ f(m) \,=\, \dfrac{(mn)!}{m!\,(n!)^{\,m}}\ \Rightarrow\ \dfrac{f(m\!+\!1)}{f(m)} \,=\, {mn\!+\!n\!-\!1\choose n\!-\!1}\in \Bbb Z\ \quad {\bf QED}$

Remark $\ $ Note that multiplicative telescopy reduces the proof to a trivial mechanical calculation. Absolutely no ingenuity is required. Computer algebra systems can easily construct such proofs.

If we write out the product obtained from the telescopy we obtain

$$\rm \dfrac{(mn)!}{m!\,(n!)^{\,m}}\ =\ {n\!-\!1\choose n\!-\!1}{2n\!-\!1\choose n\!-\!1} {3n\!-\!1\choose n\!-\!1}\cdots {(m\!+\!1)n\!-\!1\choose n\!-\!1}$$

This is equivalent to the product that L.F. stated since

$$\rm \frac{1}k {kn\choose n}\, =\, \frac{(kn)!}{k\, n!\, (kn\!-\!n)!} \,=\, \frac{kn (kn\!-\!1)!}{kn \,(n\!-\!1)!\, (kn\!-\!n)!} \,=\, {kn-1\choose n-1}$$