Combinatorics identity 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 ?
 A: 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$.
A: $\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}
$$
