Prove that $\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n$

Question

I am trying to find a combinatorial proof for the following expression $$\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n.$$

I have been stuck on this for a while, is there anyone who can help me? Thanks!

Answer 1

We have $n$ people, and want to divide them into three labelled groups, not necessarily of the same size, with some possibly empty.

This can be done in $3^n$ ways. For let the group labels be $1,2,3$. An assignment of people to these groups can be thought of as a function from the set of people to $\{1,2,3\}$. And there are $3^n$ functions from the set of $n$ people to the set $\{1,2,3\}$.

Or else line up the people in order of student number. An assignment of people to groups can be thought of as a "word" of length $n$ over the alphabet $\{1,2,3\}$. There are $3^n$ such words.

We now count the number of ways in another way.

The multinomial coefficient $\binom{n}{a_1,a_2,a_3}$ counts the number of ways to choose $a_1$ people for Group $1$, $a_2$ for Group $2$, and the rest for Group $3$. Summing gives all the ways to divide into $3$ labelled groups. Alternately, $\binom{n}{a_1,a_2,a_3}$ counts the number of words of length $n$ that have $a_1$ $1$'s, $a_2$ $2$'s, with the rest $3$'s.