32
$\begingroup$

Let $m$ be a positive integer and $n$ a nonnegative integer. Prove that

$$(n!)\cdot(m!)^n|(mn)!$$

I can prove it using Legendre's Formula, but I have to use the lemma that

$$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} \in \mathbb{N} $$

I believe that it can be proved using the lemma, since in this answer of Qiaochu Yuan he has mentioned so at the end of his answer.

Any help will be appreciated.
Thanks.

$\endgroup$
2
  • 4
    $\begingroup$ That looks like a multinomial coefficient (which you probably already know). $\endgroup$ Dec 14, 2015 at 7:15
  • 3
    $\begingroup$ @martycohen: $\frac{(mn)!}{(m!)^n}$ is a multinomial coefficient. That it is divisible by $n!$ is not as immediately obvious (to me, at least). $\endgroup$
    – robjohn
    Feb 12, 2016 at 9:59

8 Answers 8

18
$\begingroup$

Consider you have $mn$ balls with $n$ different colors and $m$ balls of each color. The number of possible arrangements is $$(mn)!\over (m!)^n$$.

However each arrangement has $n!$ "symmetric arrangements", that is, if we exchange color between whole groups we obtain a symmetric arrangement. I.E. for example if we have three color R,G,B, then $RGRBGB$ and $GRGBRB$ are symmetric arrangement by exchanging colors $R$ and $G$.

Thus $(mn)!\over (m!)^n$ is a multiple of $n!$.

$\endgroup$
3
  • 5
    $\begingroup$ Where does this use OP's lemma? $\endgroup$ Dec 14, 2015 at 7:32
  • $\begingroup$ The lemma is the same thing as the possible arrangement of $mn$ balls by letting $a_i=m$ for all $i$. But in order to prove the resulting integer is a multiple of $n!$ one needs to consider symmetric arrangements as well. $\endgroup$
    – cr001
    Dec 14, 2015 at 7:43
  • $\begingroup$ @cr001: I have some doubts about the validity of your arguments. I think in the current situation a combinatorial proof should provide a bijective mapping to a subset of the whole set and the size of the whole set should be an integral multiple of this subset. But the symmetry argument with recoloring the objects is a kind of reusage of already considered objects, so that no longer a bijection to a subset is given. $\endgroup$
    – epi163sqrt
    Dec 16, 2015 at 12:20
13
+100
$\begingroup$

Taken from this answer: $$ \begin{align} \frac{(m(n+1))!}{(m!)^{n+1}(n+1)!} &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m)}{m!(n+1)}\\ &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m-1)}{(m-1)!}\\ &=\frac{(mn)!}{(m!)^nn!}\binom{m(n+1)-1}{m-1}\tag{1} \end{align} $$ Inductively, from $(1)$ we get the formula $$ \bbox[5px,border:2px solid #C0A000]{\frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}}\tag{2} $$


By the Lemma, $$ \begin{align} \binom{mk-1}{m-1} &=\frac{(mk-1)!}{(m-1)!(mk-m)!}\\ &\in\mathbb{N}\tag{3} \end{align} $$ Therefore, $(2)$ is a product of integers, and so, an integer.

$\endgroup$
1
  • $\begingroup$ would the downvoter care to comment? $\endgroup$
    – robjohn
    Feb 28, 2016 at 10:20
7
$\begingroup$

Let $a,b$ be non-negative integers. Since ${b+a\choose a}=\frac{(b+a)!}{a!\;b!}$ is an integer, we know that $$a!\;|\;(b+1)\cdot\ldots\cdot(b+a)={b+a\choose a}\;/\;b! \tag{*}$$

Now we use induction on $n$ to solve the original problem.

For $n=0$, the statement is trivially true. Suppose it holds for $n-1$ where $n \ge 1$. Then we have

$$\begin{align} n! \cdot (m!)^n &= n\cdot m!\cdot\left((n-1)!\cdot(m!)^{n-1}\right)\\ &\stackrel{hyp.}|n\cdot m! * (mn - m)!\\ &=n\cdot m!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn)\right)\\ &=(m-1)!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn-1)\right)\\ &\stackrel{(*)}|(mn)! \end{align}$$

$\endgroup$
6
$\begingroup$

Using the Lemma, it can be seen that $\dbinom{m}{r}$ is a positive integer, since,

$\dbinom{m}{n} = \dfrac{(m)!}{n!(m-n)!}$

Now, for positive integers $r$ and $m$, consider, the quantity

$$\dfrac{1}{r} \dbinom{rm}{m}$$

Since $\displaystyle \dbinom{m}{r} = \dfrac{m}{r} \dbinom{m-1}{r-1}$,

$$\implies \dfrac{1}{r} \dbinom{rm}{m} = \dbinom{rm-1}{m-1} \tag{1}$$

Thus, by $(1)$,

$\displaystyle \dfrac{1}{r}\dbinom{rm}{m} \in \mathbb{N} $

Let $\displaystyle \text{P} = \prod_{r=1}^{n} \dfrac{1}{r} \dbinom{rm}{m}$

$\displaystyle = \prod_{r=1}^{n} \dfrac{(rm)!}{[(r-1)m!](m!)r}$

$\displaystyle = \dfrac{1}{n! (m!)^n} \prod_{r=1}^{n} \dfrac{(rm)!}{((r-1)m!)} \tag{*} $

Note that $(*)$ telescopes, thus,

$\displaystyle \text{P} = \dfrac{(mn)!}{(m!)^n n!}$

But, since $\text{P}$ is a product of positive integers, it is itself a positive integer.

$$\displaystyle \implies \dfrac{(mn)!}{(m!)^n n!} \in \mathbb{N} \qquad \square$$

$\endgroup$
2
  • $\begingroup$ There was a similar problem in IIT-JEE. You can also solve combinatorially i.e. by taking arrangements. $\endgroup$ Feb 12, 2016 at 15:55
  • $\begingroup$ The OP has specifically asked for a proof that uses the Lemma. Hence, I solved it this way. $\endgroup$
    – MathGod
    Feb 14, 2016 at 11:11
4
$\begingroup$

In fact this follows from Lagrange's Theorem: the wreath product $S_m\wr S_n$ is a subgroup of the symmetric group $S_{mn}$. One may view $S_m\wr S_n$ as the set of permutations which preserve the set partition $\{\{1,\cdots,m\},\{m+1,\cdots,2m\},\cdots,\{(n-1)m+1,\cdots,nm\}\}$. If we call the parts of this partition $X_1,\cdots,X_n$, then choosing an element of the stabilizer amounts to choosing a permutation $\sigma:\{1,\cdots,n\}\to\{1,\cdots,n\}$ and then for each $1\le i\le n$ choosing a bijection $X_i\to X_{\sigma(i)}$, so there are $n! m!^n$ elements in the stabilizer.

$\endgroup$
4
$\begingroup$

We organise the $m\cdot n$ factors of $(mn)!$ into $n$ blocks of size $m$ \begin{align*} ((j-1)&m+1)((j-1)m+2)\cdots((j-1)m+m)\tag{1}\\ &=((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\qquad 1\leq j \leq n \\ \end{align*}

Since for $0\leq m \leq k$ \begin{align*} \binom{k}{m}&=\frac{k!}{m!(k-m)!}\\ &=\frac{(k-m+1)\cdot(k-m+2)\cdots(k-1)\cdot k}{m!}\in\mathbb{N} \end{align*} the product of $m$ consecutive integers $\geq 1$ is divided by $m!$. From (1) we conclude that for $1\leq j\leq n$ \begin{align*} j( m!)\left|((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{2} \end{align*} since $jm!=(jm)(m-1)!$ and $(m-1)!$ divides the product \begin{align*} \prod_{k=1}^{n-1}(((j-1)m+k)\qquad\qquad 1\leq j \leq n \end{align*} of the $m-1$ consecutive numbers $(j-1)m+k, (k=1,\ldots,m-1)$.

$$ $$

We conclude:

\begin{align*} n!(m!)^n&=\left(\prod_{j=1}^nj\right)\left(\prod_{j=1}^nm!\right)\\ &=\prod_{j=1}^n(m-1)!(mj)\\ &\left|\ \prod_{j=1}^n((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{3}\\ &=(nm)!\\ \end{align*}

Comment:

  • In (3) we use the divisibility property (2)
$\endgroup$
1
$\begingroup$

I believe that you misinterpreded Qiaochu's words and that what he called "basic lemma" is Lagrange's theorem.

Indeed, think $\{1,\dots,mn\}$ as the disjoint union of $n$ blocks of size $m$ in the obvious way. Then $K:=S_m\times\cdots\times S_m$ ($n$ times) is a subgroup of $S_{mn}$, where the $k$-th factor consists of the permutations of the $k$-th block $\{(k-1)m+1,\dots,km\}$. So $K$ consists of permutations acting on each block separately.

On the other hand, consider the subgroup $L$ of $S_{mn}$ consisting of the permutations of the blocks, leaving the elements of each block in the same order. For instance, the cyclic permutation $\sigma$ of the blocks given by $\sigma((k-1)m+j):=km+j$ if $1\le k<n$ and $1\le j\le m$, and $\sigma((n-1)m+j):=j$ (for $k=n$), is an element of $L$.

Now, $L$ is patently isomorphic to $S_n$ and normalizes $K$, meaning that $\tau K\tau^{-1}=K$ for all $\tau\in L$. Also, $K\cap L=\{\operatorname{id}\}$. From this it follows easily (why?) that $KL$ is a subgroup of $S_{mn}$ of order $|K||L|=(m!)^n\cdot n!$, and we are done by Lagrange's theorem.

$\endgroup$
5
  • 1
    $\begingroup$ It is not true that "$\sigma$ commutes with any permutation in $K$"; a permutation in $K$ keeps blocks fixed as sets, but it can permute each block differently. I know what you mean, but it's normalization (that is, $\sigma K \sigma^{-1} = K$), not centralization :) $\endgroup$ Aug 14, 2019 at 17:20
  • $\begingroup$ Ah, you are right, that's what I meant! Edited $\endgroup$
    – Mizar
    Aug 26, 2019 at 11:43
  • $\begingroup$ I realized I misread the question and refined my answer to reflect that... $\endgroup$
    – Mizar
    Aug 26, 2019 at 12:16
  • $\begingroup$ Nice -- just perhaps say explicitly what "block" means. $\endgroup$ Aug 26, 2019 at 12:31
  • $\begingroup$ Done, thank you! $\endgroup$
    – Mizar
    Aug 26, 2019 at 12:55
0
$\begingroup$

What about using induction? Trivially true for $m = 1$, since $n! (1!)^m | (1n)!$

Assume true for $m = k$, then $n! (k!)^n$ | $((k)!)^n$, i.e. there is an integer $\lambda$ s.t. $n! (k!)^n$ = $((k)!)^n$.

Then let $k \to k+1$ and seen to be true if true for k.

$\endgroup$
1
  • $\begingroup$ Sorry, there is already an answer using induction here and I specifically want an answer that uses the lemma I have stated in my question. $\endgroup$
    – Henry
    Feb 11, 2016 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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