Solving multi-nominal equation combinatorial way

Question

I need to prove in a combintorical way the next equation:

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

What's the right combinatorical way in which i need to look on this kind of equations? (Any kind of multi-nominal equations)

Answer 1

We count the number of words of length $n$ using the alphabet $\{x,y,z\}$. It is clear that there are $3^n$ such words.

But for any $a_1,a_2,a_3$ such that $a_1+a_2+a_3=n$, there are $\binom{n}{a_1,a_2,a_3}$ words with exactly $a_1$ $x$'s, $a_2$ $y$'s, and $a_3$ $z$'s. For there are by definition $\binom{n}{a_1,a_2,a_3}$ ways to decide where the $a_1$ $x$'s, $a_2$ $y$'s, and $a_3$ $z$'s go.

So the number of words is $$\sum_{a_1+a_2+a_3=n} \binom{n}{a_1,a_2,a_3}.$$ We have counted the same thing in two different ways: the answers must be the same.

If you are algebraically inclined, note the following generalization of the Binomial Theorem. $$(x+y+z)^3=\sum_{a_1+a_2+a_3=n}\binom{n}{a_1,a_2,a_3}x^{a_1}y^{a_2}z^{a_3}.$$ To get your identity, put $x=y=z=1$.

The above formula generalizes readily. In its general form, it is called the Multinomial Theorem**.

If you don't like words, we can count the number of ways to distribute $n$ different presents among $3$ kids.