Combinatorics identity

Question

Let $a, b, c$ be positive integers. Deduce a formular for $$\sum_{i, j, k \geq 0 \\ i + j + k =n} {a\choose i}{b \choose j}{c \choose k}. $$

I think it should be $${a+b+c}\choose n$$

Proof. Let $A = \{a_i : 1 \leq i \leq a\}, B = \{b_i : 1 \leq i \leq b\}, C=\{c_i : 1 \leq i \leq c\}$ such that they are mutually disjoint. Let $D = A \cup B \cup C.$ Then $$\#ways \ to \ choose \ n \ elements \ from \ D = {{a+b+c}\choose {n}}.$$ Another way to do is to choose $i$ elements form $A$, $j$ elements form $B$ and $k$ elements from $C$ such that $i + j + k = n$. Sum over all possibility to get $$\sum_{i, j, k \geq 0 \\ i + j + k =n} {a\choose i}{b \choose j}{c \choose k} = {{a+b+c}\choose{n}}.$$

Is it correct ?

Answer 1

Your calculation is correct.

Here is an algebraic proof based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain for $a,b,c\geq 0$ and $0\leq n\leq a+b+c$

\begin{align*} \binom{a+b+c}{n}&=[x^n](1+x)^{a+b+c}\\ &=[x^n](1+x)^a(1+x)^b(1+x)^c\\ &=[x^n]\sum_{i=0}^a\binom{a}{i}x^i(1+x)^b(1+x)^c\tag{1}\\ &=\sum_{i=0}^n\binom{a}{i}[x^{n-i}]\sum_{j=0}^b\binom{b}{j}x^j(1+x)^c\tag{2}\\ &=\sum_{i=0}^n\sum_{j=0}^{n-i}\binom{a}{i}\binom{b}{j}[x^{n-i-j}]\sum_{k=0}^c\binom{c}{k}x^k\tag{3}\\ &=\sum_{i=0}^n\sum_{j=0}^{n-i}\binom{a}{i}\binom{b}{j}\binom{c}{n-i-j}\tag{4}\\ &=\sum_{{i+j+k=n}\atop{i,j,k\geq 0}}\binom{a}{i}\binom{b}{j}\binom{c}{k}\qquad\qquad\qquad\qquad\qquad n\geq 0\tag{5} \end{align*} and the claim follows.

Comment:

• In (1) we apply the binomial theorem.

• In (2) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*} We also set the upper limit of the sum to $n$, since the exponent $n-i$ of $x$ has to be non-negative.

• In (3) we do same step with $(1+x)^b$ as we did in (2).

• In (4) we select the coefficient of $[x^{n-i-j}]$.

• In (5) we set $k:= n-i-j$ and sum over $i,j,k\geq 0$ by noting that $\binom{p}{q}=0$ if $q>p$.

Answer 2

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{{\large{j,\ k,\ \ell\ \geq\ 0\ \atop j\ +\ k\ +\ \ell\ =\ n}}} {a \choose j}{b \choose k}{c \choose \ell} & = \sum_{j,\ k,\ \ell\ \geq\ 0} {a \choose j}{b \choose k}{c \choose \ell}\ \overbrace{\oint_{\verts{z}\ =\ 1^{-}} {1 \over z^{n + 1 - j - k - \ell}}\,{\dd z \over 2\pi\ic}} ^{\ds{\bracks{j + k + \ell = n}}} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{n + 1}} \bracks{\sum_{j = 0}^{\infty}{a \choose j}z^{j}} \bracks{\sum_{k = 0}^{\infty}{b \choose k}z^{k}} \bracks{\sum_{\ell = 0}^{\infty}{c \choose \ell}z^{\ell}}\,{\dd z \over 2\pi\ic} \\[5mm] & = \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} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{a + b + c} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} = \bbox[8px,border:0.1em groove navy]{a + b + c \choose n} \end{align}

The last expression is found by expanding, in powers of $\ds{z}$, $\ds{\pars{1 + z}^{a + b + c}}$. The only contribution to

the integral comes from the '$\ds{z^{n}\!}$-term' of $\ds{\pars{1 + z}^{a + b + c}}$. Namely,

$$ \bracks{z^{n}}\pars{1 + z}^{a + b + c} = {a + b + c \choose n} $$