Show that if $a$ and $b$ are positive integers then, $(a!)^b \cdot (b!)\mid (ab)!$

Question

Show that if $a$ and $b$ are positive integers then, $(a!)^b \cdot (b!)\mid(ab)!$.

Which is equivalent to prove that $(a!)^b\mid (b+1)(b+2) \cdots (ab)$

Answer 1

Any product of $n$ consecutive integers is a multiple of $n!$. So if we group the $ab$ factors of $(ab)!$ into $b$ groups of $a$ consecutive factors, $c_k=((k-1)a+1)\cdot\ldots\cdot(ka)$, $1\le k\le b$, we see that $\frac{c_k}{ka}$ is a multiple of $(a-1)!$, so $c_k=d_k\cdot a!\cdot k$. Hence $$(ab)!=\prod_{k=1}^b c_k= \prod_{k=1}^b d_ka!k=a!^b\cdot b!\cdot \prod_{k=1}^b d_k.$$

Answer 2

The counting argument is to show that the number of ordered partitions of a set of $ab$ elements into sets of $a$ elements is:

$$\frac{(ab)!}{(a!)^b}=\binom{ab}{a,a,a,\dots,a}$$

The number of unordered partitions is this value divided by $b!$ - that is, the equivalence classes of these ordered partitions all contain $b!$ elements.

An induction proof might be possible. If

$$\frac{(ab)!}{(a!)^bb!}$$ is an integer., then:

$$\frac{(a(b+1))!}{(a!)^{b+1}(b+1)!}=\frac{(ab)!}{(a!)^bb!}\cdot \frac{(ab+1)(ab+2)\cdot(ab+a)}{a!(b+1)}$$

Then we show:

$$\frac{(ab+1)(ab+2)\cdot(ab+a)}{a!(b+1)}$$ is an integer (which is essentially what Hagen's answer did, I just realized.)

Answer 3

Inductive step from Thomas Andrews' answer: $$ \begin{align} \frac{(a(b+1))!}{(a!)^{b+1}(b+1)!} &=\frac{(ab)!}{(a!)^bb!}\frac{(ab+1)(ab+2)\cdots(ab+a)}{a!(b+1)}\\ &=\frac{(ab)!}{(a!)^bb!}\frac{(ab+1)(ab+2)\cdots(ab+a-1)}{(a-1)!}\\ &=\frac{(ab)!}{(a!)^bb!}\binom{a(b+1)-1}{a-1}\tag{1} \end{align} $$ From $(1)$ we get the formula $$ \frac{(ab)!}{(a!)^bb!}=\prod_{k=1}^b\binom{ak-1}{a-1}\tag{2} $$

Answer 4

Consider a set $X$ of $ab$ elements. Partition $X$ into $b$ subsets $X_1, \dots SX_b$ of $a$ elements each. Consider the group $G = S_b \rtimes (S_a)^b$, where $S_b$ acts on $(S_a)^b = S_a \times \dots \times S_a$ by permuting the factors.

If we let each factor of $S_a$ act on one of the subsets $X_1, \dots, X_b$, and let $S_b$ act by permuting the subsets $X_1, \dots, X_b$, these actions interact in the right way to define a faithful action of $G$ on $X$, in other terms an embedding $G \hookrightarrow S_{ab}$, so by Lagrange's theorem $(b!)^a a!=|G| \mid |S_{ab}|=(ab)!$