6
$\begingroup$

(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?

$\endgroup$
  • 3
    $\begingroup$ Marlu once suggested using the obvious injective group map $S_a × S_b → S_{a+b}$. Do you consider this combinatorial? $\endgroup$ – k.stm Feb 2 '16 at 8:39
  • $\begingroup$ @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. $\endgroup$ – goblin Feb 2 '16 at 8:45
  • $\begingroup$ Anything wrong with proving the recursive formula? $\endgroup$ – darij grinberg Feb 2 '16 at 8:57
  • $\begingroup$ @darijgrinberg, that sounds good. $\endgroup$ – goblin Feb 2 '16 at 8:59
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What does those square brackets mean? $\endgroup$ – goblin Feb 2 '16 at 8:42
  • $\begingroup$ @goblin: Old-fashioned notation for the floor function. $\endgroup$ – Brian M. Scott Feb 2 '16 at 8:43
  • $\begingroup$ @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$? $\endgroup$ – goblin Feb 2 '16 at 8:45
  • $\begingroup$ @goblin: Yes, it is. $\endgroup$ – Brian M. Scott Feb 2 '16 at 8:47
  • $\begingroup$ @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. $\endgroup$ – goblin Feb 2 '16 at 9:00
9
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

With the settings

\begin{align*} [k]_q:=\frac{1-q^k}{1-q}\qquad\text{and}\qquad [k]_q!:=\prod_{j=1}^{k}[j]_q=\prod_{j=1}^{k}\frac{1-q^j}{1-q} \end{align*}

the q-binomial coefficient $\begin{bmatrix}a+b\\a\end{bmatrix}_q$ is defined as

\begin{align*} \begin{bmatrix}a+b\\a\end{bmatrix}_q:=\frac{[a+b]_q!}{[a]_q![b]_q!} \end{align*}

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.

Together with \begin{align*} \frac{(a+b)!}{a!b!}=\lim_{q\rightarrow 1}\begin{bmatrix}a+b\\a\end{bmatrix}_q \end{align*}

the claim $a!b!|(a+b)!$ follows.

$\endgroup$
2
$\begingroup$

There's a truly beautiful proof by Tim Gowers.

And a similar question has been asked before.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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