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.

How to show $(mn)!$ divides $(m!)^n$, $m$ and $n$ is integers?

share|improve this question
    
It is wrong: Take $m=n=2$, $(mn)!=4!=24$, $(m!)^n=2!^2=4$. –  LeeNeverGup Nov 29 '13 at 8:53
    
It's wrong. Take a prime of the order of $mn$ (well, larger than $m$ is enough). It's in the prime decomposition of $(mn)!$ but certainly not in that of $(m!)^n$, if $n>1$ and $m>1$. –  Jean-Claude Arbaut Nov 29 '13 at 8:53
    
This might be backwards. If $n>m$ and $n$ is a prime, then it will be false. –  Kevin Nov 29 '13 at 8:56
add comment

5 Answers

I presume you mean $(m!)^n$ divides $(mn)!$?

This is a consequence of the following fact:

If $\sum a_k = M$, then $\prod (a_k!)$ divides $M!$

Their ratio is just the multinomial coefficient, and multiple proofs can be given (search this site). A simple proof is to use induction, with the binomial coefficient as the base case.

share|improve this answer
add comment

Assuming that you mean $m!^n$ divides $(mn)!$, in equation $(1)$ of this answer, it is shown that $$ \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} =\prod_{k=1}^n\binom{\displaystyle\sum_{i=1}^ka_i}{a_k} $$ If we set all the $a_i$'s to $m$, we get $$ \frac{(mn)!}{m!^n}=\prod_{k=1}^n\binom{km}{m} $$ which gives your result.

share|improve this answer
add comment

Factorials have a nice property that you can compute the exponent of any prime in their prime decomposition. The way this is done is nicely explained by Legendre's theorem. Using it also solves this problem.

In this case the power of some prime $p$ in the decomposition of $(mn)!$ is

$ \sum_{k=1} \lfloor \frac{mn}{p^k} \rfloor$

and in the case of $(m!)^n$ we get

$ \sum_{k=1} n\lfloor \frac{m}{p^k} \rfloor$

Since $a \lfloor \frac{b}{c} \rfloor \leq \lfloor \frac{ab}{c} \rfloor$ (for all positive integers $a,b,c$) every term of the latter sum is less than or equal to that of the previous one hence establishing the (corrected) statement.

share|improve this answer
add comment

This is the same as showing that combinations or binomial coefficients $\displaystyle{n\choose k}=C_n^k=\prod_{j=0}^{k-1}\frac{n-j}{1+j}$ are always natural, for all values of n and k. It all depends on proving that the product of any k consecutive numbers is always divisible through the product of the first k consecutive numbers, $1$ through k. This is obvious, since, in each sequence of $2$ consecutive numbers, exactly one is even, and one odd; in each sequence of three consecutive numbers, exactly one is ternary, while the other two aren't; in each sequence of four consecutive numbers, exactly one is quaternary, while the rest aren't; etc. Our product, $(mn)!$, can be broken up into n sequences of m consecutive terms, each such sub-product being divisible through m!, for the reasons explained above. In other words, the whole product is divisible through $(m!)^n$. QED.

share|improve this answer
add comment

Hint: $S_m \wr S_n$ is isomorphic to a subgroup of $S_{mn}$.

share|improve this answer
add comment

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.