Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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'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.

share|improve this answer
    
Amazing. I need to learn Wreath product though! –  user21436 Feb 5 '12 at 1:44
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!$. –  Noah Stein Feb 5 '12 at 2:58
    
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. –  user21436 Feb 5 '12 at 3:06
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.