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

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)$

• I proceeded with $(ab)! = b! \times (b+1) \cdots (ab)$ where the no of terms after $b!$ is $b(a-1)$ from which we can easily prove that $a!b!|(ab)!$, but got stuck afterwards. – MUH Jan 31 '16 at 14:36

## 4 Answers

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.$$

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.)

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}$$

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)!$

• I have done any advanced algebra course. So, can you please direct me to these "faithful action" and "embedding"? where can I find them (any book and which area of maths)? – MUH Feb 17 '18 at 4:44