# Does $a!b!$ always divide $(a+b)!$

Hello the question is as stated above and is given to us in the context of group theory, specifically under the heading of isomorphism and products. I would write down what I have tried so far but I have made very little progress in trying to solve this over the last few hours!

-
If it were me I would write "Yes it does, it's a binomial coefficient", context be damned. – Hammerite Jan 31 '13 at 11:31

Hint: Find an injective group homomorphism $S_a \times S_b \hookrightarrow S_{a+b}$.

-
Presumably, you mean a group injection, not a set injection. – Thomas Andrews Jan 30 '13 at 19:54
Yes, I edited my answer accordingly. – marlu Jan 30 '13 at 19:56
ahhhh so if i define an injective homomorphism then $S_a \times S_b$ will be isomorphic to the image which is then a subgroup of $S_{a+b}$ and so it is a divisor. Thanks – Ben Jan 30 '13 at 20:04

The number of ways to choose $a$ objects out of $a+b$ objects if order matters in the selection is $(a+b)\times(a+b-1)\times\cdots\times((a+b)-(a-1))=\frac{(a+b)!}{b!}$, since there are $a+b$ ways to choose the first object, $a+b-1$ ways to choose the second object from the remaining ones, and so on.

However, $a!$ permutations actually correspond to a single combination (where order is immaterial), since $a$ objects can be arranged in $a!$ ways. This means that $\frac{(a+b)!}{b!}=ka!$ for some integer $k$, so that $(a+b)!=ka!b!$.

-
Isn't this kind of circular reasoning? How do we know that formula is the number of ways to choose $a$ objects out of $a+b$ objects? Can you prove this without proving the formula yields an integer along the way? – MartianInvader Jan 30 '13 at 21:33
This still feels like it leaves out the important details... like someone asking "Why does the order of a subgroup divide the order of the group" and someone answering "Because of Lagrange's theorem." – MartianInvader Jan 30 '13 at 21:45
I think your edit made it less clear. – Jim Jan 31 '13 at 0:41
I really like this solution...It's with posts like this that I wish I could up-vote twice! ;-) – amWhy Feb 4 '13 at 1:07

A proof based on the binomial recurrence: $\frac{(a+b)!}{a!b!} ( =\binom{a+b}{a}) =: f(a,b)$ fulfills the following recurrence:

$f(a,b) = f(a-1,b) + f(a,b-1), \quad a>0,b>0$

with starting values

$f(a,0) = f(0,a) = 1, \quad a \ge 0$

so by induction for all non-negative integer values $a,b$ the function $f(a,b)=\frac{(a+b)!}{a!b!}$ is an integer value.

-
It's good that you show the definition of the combinatorial parenthetically. It's really incidental to the question posed. – Jim Jan 31 '13 at 0:42

A proof based on prime factorization:

Let $e(N,p)$, $p$ a prime, be the exponent of $p$ in the prime factorization of $N$. Then we have to show:

For all primes $p$: $e(a!,p)+e(b!,p) \le e((a+b)!,p)$.

We have

$e(n!,p) = [\frac{n}{p}] + [\frac{n}{p^2}] + \cdots, \quad$ where $[r]$ is the largest integer $\le r$.

We also have

$[\frac{a}{k}] + [\frac{b}{k}] \le [\frac{a+b}{k}] \quad$ for any positive integers $a,b,k$.

From these two propositions the claim follows directly.

-
If we define $\sigma_p(n)$ to be the sum of the base-$p$ digits of $n$, then $$e(n!,p)=\frac{n-\sigma_p(n)}{p-1}$$ – robjohn Jan 30 '13 at 21:04
@robjohn and coproc: Would you mind giving proofs for both of your expressions for $e(n!,p)$? – Hans Jan 3 '14 at 17:24
@Hansen: my formula is proven in this answer. – robjohn Jan 3 '14 at 20:11