31
$\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$
  • 4
    $\begingroup$ That looks like a multinomial coefficient (which you probably already know). $\endgroup$ – marty cohen Dec 14 '15 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 '16 at 9:59
15
$\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$
  • 5
    $\begingroup$ Where does this use OP's lemma? $\endgroup$ – Brandon Thomas Van Over Dec 14 '15 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 '15 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$ – Markus Scheuer Dec 16 '15 at 12:20
12
+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$
  • $\begingroup$ would the downvoter care to comment? $\endgroup$ – robjohn Feb 28 '16 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$
5
$\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!](n!)r}$

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

Note that $(*)$ telescopes, thus,

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

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

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

$\endgroup$
  • $\begingroup$ There was a similar problem in IIT-JEE. You can also solve combinatorially i.e. by taking arrangements. $\endgroup$ – Aditya Kumar Feb 12 '16 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 '16 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$
  • 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$ – darij grinberg Aug 14 at 17:20
  • $\begingroup$ Ah, you are right, that's what I meant! Edited $\endgroup$ – Mizar Aug 26 at 11:43
  • $\begingroup$ I realized I misread the question and refined my answer to reflect that... $\endgroup$ – Mizar Aug 26 at 12:16
  • $\begingroup$ Nice -- just perhaps say explicitly what "block" means. $\endgroup$ – darij grinberg Aug 26 at 12:31
  • $\begingroup$ Done, thank you! $\endgroup$ – Mizar Aug 26 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$
  • $\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 '16 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.