5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – MUH Jan 31 '16 at 14:36
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – MUH Feb 17 '18 at 4:44

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.