5
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ How about using Legendre’s formula? $\endgroup$ – Mindlack Aug 13 '19 at 7:16
  • $\begingroup$ Fun fact: there's a combinatorial interpretation of the quotient as the size of a wreath product. $\endgroup$ – runway44 Aug 13 '19 at 7:16
  • $\begingroup$ I am sorry, I am not familiar with the term "wreath product". $\endgroup$ – Sabhrant Aug 13 '19 at 7:22
  • $\begingroup$ @Mindlack, I was thinking about using Legendre's formula, but how will you apply it in this case? $\endgroup$ – Sabhrant Aug 13 '19 at 7:24
  • $\begingroup$ 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 $\endgroup$ – Henry Aug 13 '19 at 7:57
2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ – erdoswiles Aug 13 '19 at 8:05
  • 1
    $\begingroup$ @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}$$ $\endgroup$ – TheSimpliFire Aug 13 '19 at 8:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.