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$
4
  • 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, 2016 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$ Feb 2, 2016 at 8:45
  • $\begingroup$ Anything wrong with proving the recursive formula? $\endgroup$ Feb 2, 2016 at 8:57
  • $\begingroup$ @darijgrinberg, that sounds good. $\endgroup$ Feb 2, 2016 at 8:59

5 Answers 5

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$
5
  • $\begingroup$ What does those square brackets mean? $\endgroup$ Feb 2, 2016 at 8:42
  • $\begingroup$ @goblin: Old-fashioned notation for the floor function. $\endgroup$ Feb 2, 2016 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$ Feb 2, 2016 at 8:45
  • $\begingroup$ @goblin: Yes, it is. $\endgroup$ Feb 2, 2016 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$ Feb 2, 2016 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
  • 2
    $\begingroup$ More directly, $(a+b)!$ factors in sequences of $a$ and $b$ consecutive integers. This immediately generalizes to the multinomial coefficients. $\endgroup$
    – user65203
    Feb 2, 2016 at 9:59
  • 1
    $\begingroup$ Huh, didn't think that far. Nice! $\endgroup$
    – MonadBoy
    Feb 2, 2016 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.