Problem on factorials and divisiblity of number theory

Question

How do I prove that $a!b!$ completely divides $(a+b)!$

Answer 1

The existing answers are sufficient to answer the question: the binomial coefficient $\binom{a+b}{a}$ is an integer and by expanding the definition it implies the divisibility condition in the question. However, there is a more "get your hands dirty" approach to solving this, that might give you some insight into number theory. So I'll include it here.

Note that $a!$ and $b!$ both clearly divide $(a + b)!$ Let's divide by $a!$ and call the result $M$:

$$\dfrac{(a + b)!}{a!} = (a + b)(a + b - 1) \dots (a + 1) = M$$

Note that $M$ is the product of $b$ consecutive terms. It now remains to show that $M$ is divisible by $b!$ Equivalently, we want to show that the exponent to which each prime $p$ appears in $b!$ is less than or equal its exponent in $M$. This is an equivalent definition of divisibility.

Now, it is a well-known result of Legendre that the exponent of a prime $p$ in $b!$ is given by:

$$\sum_{i=1}^{\infty}\lfloor\frac{b}{p^i}\rfloor$$

That is, for each $i$, we calculate the number of multiples of $p^i$ that are in the range $[1, b]$ and sum over all $i$.

Now, let's focus on the term $M$. Similarly, we can calculate the exponent of $p$ in this by calculating the number of multiples of $p^i$ that are in the range $[a + 1, a + b]$, and summing over all $i$. But from a consideration of congruences (modular arithmetic), we can see there must be a multiple of $p^i$ in the range $[a + 1, a + p^i]$. Extending this argument, we have for all $k$ that there are at least $k$ multiples of $p^i$ in the range $[a + 1, a + kp^i]$. But then there must be at least $\lfloor\frac{b}{p^i}\rfloor$ multiples of $p^i$ in the range $[a + 1, a + \lfloor\frac{b}{p^i}\rfloor\cdot p^i]$. So clearly there are at least $\lfloor\frac{b}{p^i}\rfloor$ multiples of $p^i$ in the range $[a + 1, a + b]$. And so, the exponent of $p$ in $M$ is at least:

$$\sum_{i=1}^{\infty}\lfloor\frac{b}{p^i}\rfloor$$

which concludes our proof of divisibility.

Answer 2

$$\binom{a+b}{a}=\frac{(a+b)!}{a!b!}\in\mathbb{N}$$

Answer 3

$\dfrac{(a+b)!}{a!b!}$ is the number of all possible words formed with $a$ letters $A$ and $b$ letters $B$.