# Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.)

Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for all $a$ and $b$, we have $$a! \cdot b! \mid (a+b)! \qquad?$$

Basically, I want a proof that just uses some clever algebra.

I was thinking that maybe we can use modular arithmetic, and try to understand the value of $(a+b)!$ modulo $a! \cdot b!$, and eventually show that this is $0$.

Ideas, anyone?

• Marlu once suggested using the obvious injective group map $S_a × S_b → S_{a+b}$. Do you consider this combinatorial? – k.stm Feb 2 '16 at 8:39
• @k.stm, its too combinatorial to classify as an answer, but also sounds very interesting. I'd be curious to see that reference, for sure. Edit. Thanks, that is a nice argument. – goblin Feb 2 '16 at 8:45
• Anything wrong with proving the recursive formula? – darij grinberg Feb 2 '16 at 8:57
• @darijgrinberg, that sounds good. – goblin Feb 2 '16 at 8:59

You can use $\nu_{p}(n!)=\sum \limits_{k\ge 1}\left[\dfrac{n}{p^k}\right]$ and that $[a+b]\ge [a]+[b]$

• What does those square brackets mean? – goblin Feb 2 '16 at 8:42
• @goblin: Old-fashioned notation for the floor function. – Brian M. Scott Feb 2 '16 at 8:43
• @BrianM.Scott, thanks. And just be completely certain, I'm assuming $\nu_p(m)$ is the number of factors of $p$ in the prime factorization of $m$? – goblin Feb 2 '16 at 8:45
• @goblin: Yes, it is. – Brian M. Scott Feb 2 '16 at 8:47
• @bof, k.stm linked to a similar question. I don't think they're perfect dupes though, and I'm hopeful that more interesting stuff will be posted here. – goblin Feb 2 '16 at 9:00

If we use as a lemma that the product of $k$ consecutive integers is divisible by $k!$ (proven e.g. here: The product of n consecutive integers is divisible by n factorial), we see that $(a+b)!/a!$ factors into the $b$ consecutive integers $a+1,\ldots,a+b$, hence is divisible by $b!$. Then $a!b!|(a+b)!$.

• More directly, $(a+b)!$ factors in sequences of $a$ and $b$ consecutive integers. This immediately generalizes to the multinomial coefficients. – Yves Daoust Feb 2 '16 at 9:59
• Huh, didn't think that far. Nice! – A.Sh Feb 2 '16 at 10:19

Possibly the answer that you don't want:

$$\frac{(a+0)!}{a!\cdot 0!}=1=\frac{(0+b)!}{0!\cdot b!}$$

and

$$\frac{(a+b)!}{a!\cdot b!}=\frac{(a+b)(a+b-1)!}{a!\cdot b!}=\frac{(a-1+b)!}{(a-1)!\cdot b!}+\frac{(a+b-1)!}{a!\cdot (b-1)!}.$$

Then by induction, Pascal's triangle is made of integers.

With the settings

the q-binomial coefficient $\begin{bmatrix}a+b\\a\end{bmatrix}_q$ is defined as
Since the following is valid \begin{align*} \begin{bmatrix}a+b\\a\end{bmatrix}_q&=\begin{bmatrix}a+b-1\\a\end{bmatrix}_q+q^{b}\begin{bmatrix}a+b-1\\a-1\end{bmatrix}_q\\ \begin{bmatrix}a\\0\end{bmatrix}_q&=\begin{bmatrix}a\\a\end{bmatrix}_q=1 \end{align*} the $q$-binomial coefficients are polynomials in $q$ with non-negative integer coefficients.
the claim $a!b!|(a+b)!$ follows.