# How to show $(mn)!$ is divisible by $(m!)^n$?

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

• 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

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.

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.

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.

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.

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

• What does $\wr$ mean, please? I don't think I've ever seen that symbol before. – saulspatz Feb 19 at 19:15
• It denotes the wreath product between two groups. – Seirios Mar 15 at 19:20