4
$\begingroup$

Let $a$, $b$, $c$ and $n$ be non-negative integers.

By counting the number of committees consisting of $n$ sentient beings that can be chosen from a pool of $a$ kittens, $b$ crocodiles and $c$ emus in two different ways, prove the identity

$\sum\limits_{\substack{i,j,k \ge 0; \\ i+j+k = n}} {{a \choose i}\cdot{b \choose j}\cdot{c \choose k} = {a+b+c \choose n}}$

where the sum is over all non-negative integers $i$, $j$ and $k$ such that $i+j+k=n.$

I know that this is some kind of combinatorial proof. My biggest problem is that I've never really done a proof.

3 Answers 3

5

On the righthand side, we form a committee of size $n$ by lumping all the animals together (so there are $a + b + c$ animals total) and choosing $n$ of them.

On the lefthand side, we form a committee of size $n$ by first choosing exactly $i$ kittens, $j$ crocodiles, and $k$ emus (subject to $i + j + k = n$). For fixed $i$, $j$, and $k$, there are $ \binom{a}{i}\binom{b}{j}\binom{c}{k} $ such committees. Summing over all possible partitions of the integer $n$ means we've formed the committees in every possible way, which is precisely what is counted on the righthand side.

  • 1
    @barrowspizza It co$u$ld be written more clearly, but it has enough detail *for me*. Whether it has enough detail *for you* or *for your professor* (if it is homework) my be completely different standards.2012-11-26
1

Assuming we want to choose from $a+b$ first before choosing from $c$ such that $n_a+n_b=r$ then the number of ways of choosing is ($p$ from $a$ and $r-p$ from $b$) $\sum_{p=0}^r \binom ap\displaystyle\binom b{r-p}$

Afterward $c$ can must fill $n-(n_a+n_b)=n-r$ spaces so we choose $n-r$ from $c$ and $r$ from $a+b$ which implies that one can rewrite the sum as $\sum\limits_{\substack{i,j,k \ge 0;\\ i+j+k = n}} {a \choose i}\cdot{b \choose j}\cdot{c \choose k} = \sum_{r=0}^n \binom c{n-r}\left( \sum_{p=0}^r \binom ap\binom b{r-p}\right)=\underbrace{\sum_{r=0}^n \sum_{p=0}^r \binom c{n-r} \binom ap\binom b{r-p}}$ Note that if $r>n$ then $\displaystyle \binom nr =0$, so the above expression is valid.

Product of three polynomials $\begin{array}{ll}\sum^a_{i=0}a_ix^i\cdot \sum^b_{j=0}b_jx^j\cdot\sum^c_{k=0}c_kx^k &= \sum^{a+b}_{m=0}\left( \sum_{p=0}^m a_pb_{m-p}\right)x^m \cdot\sum^c_{k=0}c_kx^k \quad\text {we use }d_m=\sum_{p=0}^m a_pb_{m-p}\\&=\sum^{a+b}_{m=0}d_mx^m \cdot\sum^c_{k=0}c_kx^k \\&= \sum^{a+b+c}_{n=0}\left( \sum_{r=0}^n d_rc_{n-r}\right)x^n =\sum^{a+b+c}_{n=0}\left( \sum_{r=0}^n c_{n-r}\left(\sum_{p=0}^r a_pb_{r-p}\right)\right)x^n\\&=\sum^{a+b+c}_{n=0} \sum_{r=0}^n \sum_{p=0}^ra_p b_{r-p}c_{n-r}\cdot x^n \quad \quad \quad (1) \end{array}$

By the binomial theorem $(1+x)^{a+b+c}$ $ \begin{array}{ll}= \sum^{a+b+c}_{n=0}\binom {a+b+c}{n}x^n\\ = (1-x)^a(1-x)^b(1-x)^c\\=\left(\sum^a_{i=0}\binom ai x^i \right)\left(\sum^b_{j=0}\binom bj x^j \right)\left(\sum^c_{k=0}\binom ck x^k \right) \\=\sum^{a+b+c}_{n=0} \underbrace{\sum_{r=0}^n \sum_{p=0}^r \binom c{n-r} \binom ap\binom b{r-p}} x^n \quad \text{after using result (1)} \end{array}$

Observe that the under-braced expression is exactly the one under-braced above and it is the coefficient of of $x^n$, we can then equate it to the coefficient binomial expansion i;e;

$\binom {a+b+c}{n}=\sum_{r=0}^n \sum_{p=0}^r \binom c{n-r} \binom ap\binom b{r-p}$

This is the Vandermonde's identity for three polynomials and it is the only combinatorial proof I know of. Thanks to Douglas S. Stones who pointed this out to me in a question I asked.

One can do the same for $4$, $5$, ... but it is exhausting so proof by induction or the one given by Austin is sufficient.

0

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{i\ +\ j\ +\ k\ =\ n \atop{\vphantom{\LARGE A}i,\ j,\ k\ \geq\ 0}} {a \choose i}{b \choose j}{c \choose k} = {a + b + c \choose n}:\ {\large ?}}$

\begin{align}&\color{#66f}{\large% \sum_{i\ +\ j\ +\ k\ =\ n \atop{\vphantom{\LARGE A}i,\ j,\ k\ \geq\ 0}} {a \choose i}{b \choose j}{c \choose k}} =\sum_{\ell_{a},\ \ell_{b},\ \ell_{c}\ \geq\ 0}{a \choose \ell_{a}} {b \choose \ell_{b}}{c \choose \ell_{c}} \delta_{\ell_{a}\ +\ \ell_{b}\ +\ \ell_{c},\ n} \\[3mm]&=\sum_{\ell_{a},\ \ell_{b},\ \ell_{c}\ \geq\ 0}{a \choose \ell_{a}} {b \choose \ell_{b}}{c \choose \ell_{c}}\oint_{\verts{z}\ =\ 1} {1 \over z^{-\ell_{a}\ -\ \ell_{b}\ -\ \ell_{c}\ +\ n\ +\ 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{n\ +\ 1}} \bracks{\sum_{\ell_{a}\ \geq\ 0}{a \choose \ell_{a}}z^{\ell_{a}}} \bracks{\sum_{\ell_{b}\ \geq\ 0}{b \choose \ell_{b}}z^{\ell_{b}}} \bracks{\sum_{\ell_{a}\ \geq\ 0}{c \choose \ell_{c}}z^{\ell_{c}}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{n\ +\ 1}} \pars{1 + z}^{a}\pars{1 + z}^{b}\pars{1 + z}^{c}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{a + b + c} \over z^{n\ +\ 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\color{#66f}{\large{a + b + c \choose n}} \end{align}