Proof by counting two ways Proof by counting two ways:
\begin{equation}\sum_{k_1+k_2+...+k_m=n}{k_1\choose a_1}{k_2\choose a_2}...{k_m\choose a_m}={n+m-1\choose a_1+a_2+...+a_m+m-1}\end{equation}
I have a proof by algebra for it, but I want to seek a proof by counting it two ways.
Can you help me?
 A: Let m just be 2. You can easily generalize later.
$$
\begin{equation}\sum_{k_1+k_2=n}{k_1\choose a_1}{k_2\choose a_2}={k_1+k_2+1\choose a_1+a_2+1}\end{equation}
$$
Think about you have $k_1+k_2+1$ students and pick $a_1+a_2+1$ students among them. RHS is just straightforward.
Then see LHS. Assume the students are sitting in a row. You first pick $1( = m - 1)$ student among them. Then pick $a_1$ students in left of the student you picked first. Also pick $a_2$ students in right of the student you picked first. Repeat this for your every possible pick of first student.
Good luck on your study!
A: Let $\ell=n-\sum_{i=1}^ma_i$; then 
$$\dbinom{n+m-1}{a_1+\ldots+a_m+m-1}$$ 
is the number of ways to distribute $\ell$ indistinguishable balls amongst $$\sum_{i=1}^ma_i+m=\sum_{i=1}^m(a_i+1)$$ distinguishable boxes. For $i=1,\ldots,m$ let $A_i$ be a distinct set of $a_i+1$ distinguishable boxes, and let $A=\bigcup_{i=1}^mA_i$.
$\binom{k_i}{a_i}$ is the number of ways to distribute $k_i+1$ indistinguishable balls amongst the $a_i+1$ distinguishable boxes in $A_i$ so that each box gets at least one ball. Thus, it’s also the number of ways to distribute $(k_i+1)-(a_i+1)=k_i-a_i$ indistinguishable balls amongst the $a_i+1$ boxes in $A_i$. It follows that
$$\sum_{k_1+\ldots+k_m=n}{k_1\choose a_1}{k_2\choose a_2}\ldots{k_m\choose a_m}$$
is the total number of ways to distribute $\ell$ indistinguishable balls amongst the $\sum_{i=1}^m(a_i+1)$ boxes in $A$, summed over all $m$-tuples $\langle\ell_1,\ldots,\ell_m\rangle$ of non-negative integers such that $\sum_{i=1}^m\ell_i=\ell$, where $\ell_i$ is the number of balls distributed amongst the $a_i+1$ boxes in $A_i$. It follows immediately that 
$$\sum_{k_1+\ldots+k_m=n}{k_1\choose a_1}{k_2\choose a_2}\ldots{k_m\choose a_m}=\binom{n+m-1}{a_1+\ldots+a_m+m-1}\;.$$
