Prove $\sum \binom{n}{a_1,\,a_2,\,a_3}=3^n$

Question

Give a combinatorial proof for:

$$\sum\binom{n}{a_1,\,a_2,\,a_3}=3^n$$

I am not getting the notations of $a_1,\,a_2,\,a_3$. Thus I'm not able to solve this question. I don't know how to do this. Help me out.

Answer 1

If the $a_i$ are non-negative integers with $a_1+a_2+a_3=n $, $\binom{n}{a_1,\,a_2,\,a_3}$ denotes the number of ways to place $n$ objects in one of three categories, with category $i$ containing $a_i$ of the objects. Summing over all solutions of $a_1+a_2+a_3=n$ gives the number of ways to categorise each objects, which of course is $3^n$.

Answer 2

This is a trinomial. In fact, we have in general: $(x_1+x_2+...x_k)^n= \sum_{\alpha} \frac {n!}{\alpha_1! \alpha_2!....\alpha_k!} x_1^{\alpha_1} x_2^{\alpha_2}...x_k^{\alpha_k}$ (where $\sum \alpha_i=n$) as the multinomial theorem. You result follows from the result for a trinomial theorem, where $x_i=1$ so it becomes $(1+1+1)^n$

Answer 3

If you divide $n$ objects into $3$ distinguishable groups of objects then for each of the $n$ objects there are $3$ choices. This tells us that $3^n$ splitups are possible.

If the number of objects in group $1,2,3$ are fixed and $a_i$ objects land in group $i$ then $a_1+a_2+a_3=n$ and there are $\frac{n!}{a_1!a_2!a_3!}$ splitups. Another notation for this number is: $$\binom{n}{a_1,a_2,a_3}$$

These considerations make us conclude that $$\sum_{(a_1,a_2,a_3)\in A}\binom{n}{a_1,a_2,a_3}=3^n$$ where $A$ denotes the set$\{(x,y,z)\in\{0,1,2\dots\}\mid x+y+z=n\}$.