Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
There is a nice proof of this using group theory. Which course are you taking? –  Geoff Robinson Feb 23 '13 at 18:44
    
@Geoff Robinson:i know concept of group theory.passed one years ago. but i didn't this question in group theory –  Maisam Hedyelloo Feb 23 '13 at 18:52
6  
There is a nice subgroup of the Symmetric group $S_{mn}$ whose order is $m!(n!)^{m}$. If you can see this, you can apply Lagrange's theorem. –  Geoff Robinson Feb 23 '13 at 18:54
    
@Geoff Robinson :excellent idea.i think making this permutation is not hard but why $$m!(n!)^{m}\le(mn)!$ –  Maisam Hedyelloo Feb 23 '13 at 19:01
1  
@GeoffRobinson: Please share yours with us. –  Babak S. Feb 23 '13 at 19:03

5 Answers 5

up vote 13 down vote accepted

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!

share|improve this answer
    
This can be derived mechanically by telescopy (see my answer). Out of curiosity, how did you derive it? –  Math Gems Feb 23 '13 at 22:22
    
@MathGems Breaking it up: $$\frac{(mn)!}{(n!)^m}=\left(\frac{(1)\cdots (n)}{n!}\right)\left(\frac{(n+1)\cdots (2n)}{n!}\right)\cdots \left(\frac{(n(m-1)+1)\cdots (mn)}{n!}\right)=\binom{n}{n}\binom{2n}{n}\cdots\binom{mn}{n}$$ Then distributing the remain $m!$ –  L. F. Feb 24 '13 at 0:12
    
Thanks, as I surmised. But I wondered if there might be other interesting viewpoints. –  Math Gems Feb 24 '13 at 0:21
    
Why exactly is $\binom{kn}{n}$ divisible by $k$? –  Caleb Jares Sep 29 '13 at 19:28
1  
@CalebJares $\binom{kn}{n}=k\binom{kn-1}{n-1}$ –  L. F. Sep 30 '13 at 0:34

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

share|improve this answer

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.

share|improve this answer
    
Thanks for doing that. Thanks Geoff. ;-) –  Babak S. Feb 24 '13 at 3:33

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.