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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.