Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Question

Let $m$ be a positive integer and $n$ a nonnegative integer. Prove that

$$(n!)\cdot(m!)^n|(mn)!$$

I can prove it using Legendre's Formula, but I have to use the lemma that

$$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} \in \mathbb{N} $$

I believe that it can be proved using the lemma, since in this answer of Qiaochu Yuan he has mentioned so at the end of his answer.

Any help will be appreciated.
Thanks.

Answer 1

Consider you have $mn$ balls with $n$ different colors and $m$ balls of each color. The number of possible arrangements is $$(mn)!\over (m!)^n$$.

However each arrangement has $n!$ "symmetric arrangements", that is, if we exchange color between whole groups we obtain a symmetric arrangement. I.E. for example if we have three color R,G,B, then $RGRBGB$ and $GRGBRB$ are symmetric arrangement by exchanging colors $R$ and $G$.

Thus $(mn)!\over (m!)^n$ is a multiple of $n!$.

Answer 2

Let $a,b$ be non-negative integers. Since ${b+a\choose a}=\frac{(b+a)!}{a!\;b!}$ is an integer, we know that $$a!\;|\;(b+1)\cdot\ldots\cdot(b+a)={b+a\choose a}\;/\;b! \tag{*}$$

Now we use induction on $n$ to solve the original problem.

For $n=0$, the statement is trivially true. Suppose it holds for $n-1$ where $n \ge 1$. Then we have

$$\begin{align} n! \cdot (m!)^n &= n\cdot m!\cdot\left((n-1)!\cdot(m!)^{n-1}\right)\\ &\stackrel{hyp.}|n\cdot m! * (mn - m)!\\ &=n\cdot m!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn)\right)\\ &=(m-1)!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn-1)\right)\\ &\stackrel{(*)}|(mn)! \end{align}$$

Answer 3

We organise the $m\cdot n$ factors of $(mn)!$ into $n$ blocks of size $m$ \begin{align*} ((j-1)&m+1)((j-1)m+2)\cdots((j-1)m+m)\tag{1}\\ &=((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\qquad 1\leq j \leq n \\ \end{align*}

Since for $0\leq m \leq k$ \begin{align*} \binom{k}{m}&=\frac{k!}{m!(k-m)!}\\ &=\frac{(k-m+1)\cdot(k-m+2)\cdots(k-1)\cdot k}{m!}\in\mathbb{N} \end{align*} the product of $m$ consecutive integers $\geq 1$ is divided by $m!$. From (1) we conclude that for $1\leq j\leq n$ \begin{align*} j( m!)\left|((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{2} \end{align*} since $jm!=(jm)(m-1)!$ and $(m-1)!$ divides the product \begin{align*} \prod_{k=1}^{n-1}(((j-1)m+k)\qquad\qquad 1\leq j \leq n \end{align*} of the $m-1$ consecutive numbers $(j-1)m+k, (k=1,\ldots,m-1)$.

$$ $$

We conclude:

\begin{align*} n!(m!)^n&=\left(\prod_{j=1}^nj\right)\left(\prod_{j=1}^nm!\right)\\ &=\prod_{j=1}^n(m-1)!(mj)\\ &\left|\ \prod_{j=1}^n((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{3}\\ &=(nm)!\\ \end{align*}

Comment:

• In (3) we use the divisibility property (2)

Answer 4

In fact this follows from Lagrange's Theorem: the wreath product $S_m\wr S_n$ is a subgroup of the symmetric group $S_{mn}$. One may view $S_m\wr S_n$ as the set of permutations which preserve the set partition $\{\{1,\cdots,m\},\{m+1,\cdots,2m\},\cdots,\{(n-1)m+1,\cdots,nm\}\}$. If we call the parts of this partition $X_1,\cdots,X_n$, then choosing an element of the stabilizer amounts to choosing a permutation $\sigma:\{1,\cdots,n\}\to\{1,\cdots,n\}$ and then for each $1\le i\le n$ choosing a bijection $X_i\to X_{\sigma(i)}$, so there are $n! m!^n$ elements in the stabilizer.

Answer 5

What about using induction? Trivially true for $m = 1$, since $n! (1!)^m | (1n)!$

Assume true for $m = k$, then $n! (k!)^n$ | $((k)!)^n$, i.e. there is an integer $\lambda$ s.t. $n! (k!)^n$ = $((k)!)^n$.

Then let $k \to k+1$ and seen to be true if true for k.

Answer 6

Using the Lemma, it can be seen that $\dbinom{m}{r}$ is a positive integer, since,

$\dbinom{m}{n} = \dfrac{(m)!}{n!(m-n)!}$

Now, for positive integers $r$ and $m$, consider, the quantity

$$\dfrac{1}{r} \dbinom{rm}{m}$$

Since $\displaystyle \dbinom{m}{r} = \dfrac{m}{r} \dbinom{m-1}{r-1}$,

$$\implies \dfrac{1}{r} \dbinom{rm}{m} = \dbinom{rm-1}{m-1} \tag{1}$$

Thus, by $(1)$,

$\displaystyle \dfrac{1}{r}\dbinom{rm}{m} \in \mathbb{N} $

Let $\displaystyle \text{P} = \prod_{r=1}^{n} \dfrac{1}{r} \dbinom{rm}{m}$

$\displaystyle = \prod_{r=1}^{n} \dfrac{(rm)!}{[(r-1)m!](m!)r}$

$\displaystyle = \dfrac{1}{n! (m!)^n} \prod_{r=1}^{n} \dfrac{(rm)!}{((r-1)m!)} \tag{*} $

Note that $(*)$ telescopes, thus,

$\displaystyle \text{P} = \dfrac{(mn)!}{(m!)^n n!}$

But, since $\text{P}$ is a product of positive integers, it is itself a positive integer.

$$\displaystyle \implies \dfrac{(mn)!}{(m!)^n n!} \in \mathbb{N} \qquad \square$$

Answer 7

Taken from this answer: $$ \begin{align} \frac{(m(n+1))!}{(m!)^{n+1}(n+1)!} &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m)}{m!(n+1)}\\ &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m-1)}{(m-1)!}\\ &=\frac{(mn)!}{(m!)^nn!}\binom{m(n+1)-1}{m-1}\tag{1} \end{align} $$ Inductively, from $(1)$ we get the formula $$ \bbox[5px,border:2px solid #C0A000]{\frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}}\tag{2} $$

---

By the Lemma, $$ \begin{align} \binom{mk-1}{m-1} &=\frac{(mk-1)!}{(m-1)!(mk-m)!}\\ &\in\mathbb{N}\tag{3} \end{align} $$ Therefore, $(2)$ is a product of integers, and so, an integer.

Answer 8

I believe that you misinterpreded Qiaochu's words and that what he called "basic lemma" is Lagrange's theorem.

Indeed, think $\{1,\dots,mn\}$ as the disjoint union of $n$ blocks of size $m$ in the obvious way. Then $K:=S_m\times\cdots\times S_m$ ($n$ times) is a subgroup of $S_{mn}$, where the $k$-th factor consists of the permutations of the $k$-th block $\{(k-1)m+1,\dots,km\}$. So $K$ consists of permutations acting on each block separately.

On the other hand, consider the subgroup $L$ of $S_{mn}$ consisting of the permutations of the blocks, leaving the elements of each block in the same order. For instance, the cyclic permutation $\sigma$ of the blocks given by $\sigma((k-1)m+j):=km+j$ if $1\le k<n$ and $1\le j\le m$, and $\sigma((n-1)m+j):=j$ (for $k=n$), is an element of $L$.

Now, $L$ is patently isomorphic to $S_n$ and normalizes $K$, meaning that $\tau K\tau^{-1}=K$ for all $\tau\in L$. Also, $K\cap L=\{\operatorname{id}\}$. From this it follows easily (why?) that $KL$ is a subgroup of $S_{mn}$ of order $|K||L|=(m!)^n\cdot n!$, and we are done by Lagrange's theorem.

Answer 9

A moment's thought convinces us that $$P_{m, n} \colon = \frac{(m n)!}{(m!)^n \cdot n!}$$ equals the number of partitions of the set $\{1, 2, \ldots, m n\}$ into $n$ subsets of size $m$.

Let's see why the formula of @robjohn

$$P_{m,n} =\binom{m n-1}{m-1}\cdot P_{m, n-1}$$

is true. Indeed, map every such partion of $[m n]$ to the subset containing $1$. There are exactly $\binom{m n-1}{m-1}$ such subsets. Now the fiber of each such element has cardinality $P_{m, n-1}$, being a partition of a set of $m(n-1)$ elements into $n-1$ parts of size $m$.