7
$\begingroup$

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?

2 Answers 2

4

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.

  • 0
    Aha! I had gotten to the last line algebraically, but that was the key I needed, thank you!2012-02-05
6

If you're not interested in non-inductive proofs, please ignore this answer.

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.

  • 0
    @KannappanSampath: Thanks!2012-02-05