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?
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.
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.