# Combinatorial Proof Of Binomial Double Counting

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.

-

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.

-
Logically that makes sense but is there some way of proving this with more than just because it makes sense. – barrowspizza Nov 25 '12 at 21:27
@barrowspizza What we need to be concerned with is that every committee gets counted exactly once by the lefthand side. Every committee is counted at least once because it will appear in the sum at whichever $i$, $j$, $k$ partition corresponds to it. A committee cannot be counted twice because there is only one such partition that corresponds to it. So, every committee is counted exactly once. – Austin Mohr Nov 25 '12 at 21:38
Can what you say be considered a proof though? I just really don't know what constitutes a proof. – barrowspizza Nov 25 '12 at 22:58
@barrowspizza It could 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. – Austin Mohr Nov 26 '12 at 0:01

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.

-

$\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}

-