# Inductive proof that $(m!^n)n! \mid (mn)!$

I have worked this problem out before but am stuck on the inductive step.

Show that $(m!^n)n! \mid (mn)!$

I am using induction on $n$.

I thought to factor $(m(n+1))$! but can't get it exactly how I want it, any suggestions?

-

Assume that $(m!^n)n\mid(mn)!$, say $(mn)!=a(m!^n)n$. Then

\begin{align*} \big(m(n+1)\big)!&=(mn+m)!\\ &=(mn)!\prod_{k=1}^m(mn+k)\\ &=a(m!^n)n!\prod_{k=1}^m(mn+k)\\ &=a(m!^n)n!(mn+m)\prod_{k=1}^{m-1}(mn+k)\\ &=am(m!^n)(n+1)!\prod_{k=1}^{m-1}(mn+k)\;. \end{align*}

If you can now show that $$(m-1)!\;\Bigg\vert\;\prod_{k=1}^{m-1}(mn+k)\;,$$ you’ll have the extra factor of $m!$ that you need.

HINT: $\dbinom{mn+m-1}{mn}$ is an integer.

-
Aha! I had gotten to the last line algebraically, but that was the key I needed, thank you! – user24372 Feb 5 '12 at 1:21

If you are, note that you can view the group $S_m\wr S_n$ (that squiggly symbol is the wreath product) as a subgroup of $S_{mn}$. These groups have cardinality $(m!)^nn!$ and $(mn)!$, respectively. The statement you want is Lagrange's theorem applied to this pair.
@KannappanSampath: While wikipedia defines $\wr$, it could perhaps be more explicit. For the purposes of this answer, view $S_{mn}$ as permutations of $mn$ items arranged in a grid with $m$ rows and $n$ columns. Then $S_m\wr S_n$ is the subgroup consisting of all permutations which rearrange columns in an arbitrary way and rearrange elements within each column in an arbitrary way. You can rearrange the $n$ columns in $n!$ ways and rearrange the elements of each of the $n$ columns in $m!$ ways, so $\lVert S_m\wr S_n\rVert = (m!)^nn!$. – Noah Stein Feb 5 '12 at 2:58
A link to your answer is posted on my profile here. Particularly a good answer. I have known applications like this: For instance $n! \mid \binom n 0 _2$, by considering the symmetric group as a subgroup in $\operatorname {GL}(\mathbb F_2)$, the homomorphism given by the permutation matrices. But, however I could not think of this, because I never knew the way to work with Wreath Product! – user21436 Feb 5 '12 at 3:12
@KannappanSampath: It looks like we both have something to learn from each other about this trick. What does the notation $\binom{n}{0}_2$ mean? – Noah Stein Feb 5 '12 at 3:41