# Show that $(a!)^b b! \mid (ab)!$ [duplicate]

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

This is what I have done:

The above statement is true for $$a=1$$ and any arbitrary value of $$b$$, and also for $$b=1$$ and any arbitrary value of $$a$$. Now for $$a \ge 2$$ and $$b\ge 2$$, $$a+b\le ab$$. This implies, $$(a+b)!\mid (ab)!$$ and since $$\dbinom{a+b}{a} = \frac{(a+b)!}{a!b!} \implies a!b!\mid (a+b)! \implies (a!b!)\mid(ab)!$$

Any ideas how to further progress in this proof? Or are there any other ways to prove this?

• How about using Legendre’s formula? – Mindlack Aug 13 '19 at 7:16
• Fun fact: there's a combinatorial interpretation of the quotient as the size of a wreath product. – runway44 Aug 13 '19 at 7:16
• I am sorry, I am not familiar with the term "wreath product". – Sabhrant Aug 13 '19 at 7:22
• @Mindlack, I was thinking about using Legendre's formula, but how will you apply it in this case? – Sabhrant Aug 13 '19 at 7:24
• Find the number of ways of arranging $ab$ balls where you have $b$ balls each of $a$ different types, but where the types are only distinguishable as "first to appear in the arrangement, second to appear ...". This is an integer – Henry Aug 13 '19 at 7:57

Induction on $$b$$ will work.
Base case: $$b=1$$ yields $$(a!)^1\cdot1!\mid(a\cdot1)!$$ which is true.
Inductive step assume for some positive integer $$k$$, we have $$(ak)!=n(a!)^k k!$$ where $$n$$ is a positive integer.
Consider $$b=k+1$$: \begin{align}(a(k+1))!&=(ak)!\cdot\frac{(ak+a)!}{(ak)!}\\&=n(a!)^k k!\binom{ak+a}{ak}\cdot a!\\&=n(a!)^{k+1}k!\cdot(k+1)\binom{ak+a-1}{ak}\\&=m(a!)^{k+1}(k+1)!\end{align} where $$m$$ is a positive integer.
Thus $$(a!)^b b!\mid (ab)!$$.
• Wouldn't it be $\binom{ak+a}{ak} = \frac{ak+a}{ak}\binom{ak+a-1}{ak-1}$, and so you would have a $k$ at the bottom? – erdoswiles Aug 13 '19 at 8:05
• @erdoswiles $$\binom{ak+a}{ak}=\frac{(ak+a)(ak+a-1)\cdots(ak+1)}{a(a-1)\cdots2\cdot1}=(k+1)\frac{(ak+a-1)\cdots(ak+1)}{(a-1)!}=(k+1)\binom{ak+a-1}{ak}$$ – TheSimpliFire Aug 13 '19 at 8:37