Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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!$.
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.
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}$$
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!](n!)r}$
$\displaystyle = \dfrac{1}{m! (n!)^m} \prod_{r=1}^{n} \dfrac{(rm)!}{((r-1)m!)} \tag{*} $
Note that $(*)$ telescopes, thus,
$\displaystyle \text{P} = \dfrac{(mn)!}{(n!)^m m!}$
But, since $\text{P}$ is a product of positive integers, it is itself a positive integer.
$$\displaystyle \implies \dfrac{(mn)!}{(n!)^m m!} \in \mathbb{N} \qquad \square$$
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.
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:
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.
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.
