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
    Amazing. I need to learn Wreath product though!2012-02-05
  • 1
    @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!$.2012-02-05
  • 0
    This sort of provides me the intuition. I meant that, I don't know the construction of the wreath product. So, I'll have to learn that formally. But, I am thankful to you for the intuition. I love your answer and the explanation.2012-02-05
  • 0
    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!2012-02-05
  • 0
    @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?2012-02-05
  • 0
    $\binom n 0_2:=|\operatorname{GL}(\mathbb F_2^n)|=(2^n-1)(2^n-2)(2^n-4) \cdots (2^n-2^{n-1}$. I am sorry that $n$ went missing in my previous comment and may have well served as the source of confusion. Particularly, this $\binom n 0_2$ is called the Gaussian Binomial 2-coefficient and a binomial $q$-coefficient for $q$ a prime power is defined in a similar way. And the limit of the coefficient as $q \to 1$ is the binomial coefficient!2012-02-05
  • 0
    @KannappanSampath: Thanks!2012-02-05