# How to prove $\sum \limits_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n$?

I am looking for a combinatorial approach to prove that $$\sum \limits_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n .$$

I am more interested in a combinatorial proof, however an algebraic one is also welcome.

-

The solution depends very much on how the multinomial coefficient $\binom{n}{k_1,k_2,\dots,k_m}$ is defined.

If it is defined as the coefficient of $x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$ in the expansion of $$(x_1+x_2+\cdots +x_m)^n,$$ then we obtain an immediate solution by setting $x_1=x_2=\cdots=x_k=1$.

Edit: After writing the answer, I wanted to insert at this point a link to the Multinomial Theorem. So I went to the Wikipedia article, and noticed that it is of surprisingly good quality. I would recommend going through it thoroughly, as an alternative superior to reading what is written below.

For a more purely "counting" approach, we can count the number of ways of distributing $n$ objects among $m$ "bins," or more concretely, $n$ presents among $n$ kids.

Or else, equivalently, we imagine an alphabet of $m$ "letters," say $a_1, a_2, \dots, a_m$, and count in two different ways the number of $n$-letter "words."

First way: The first letter can be chosen in $m$ different ways, and for every choice of first letter we can choose the second letter in $m$ different ways, and so on. Thus the total number of $n$-letter words is $m^n$.

Second way: We count the words that have $k_1$ $a_1$'s, $k_2$ $a_2$'s, and so on up to $k_m$ $a_m$'s, where $k_1+k_2+\cdots +k_m=n$, and then add up over all possible choices of $(k_1,\dots,k_m)$.

To make a word that has $k_1$ $a_1$'s, $k_2$ $a_2$'s, and so on up to $k_m$ $a_m$'s, where $k_1+\cdots +k_m=n$, we simultaneously choose the $k_1$ positions where the $a_1$'s will go, and the $k_2$ positions where the $a_2$'s will go, and so on up to the $k_m$ positions where the $k_m$ $a_m$'s will go. By one of the standard definitions of the multinomial coefficient, the number of ways to do this is precisely $\binom{n}{k_1,\dots,k_m}$. It follows that the number of words is $$\sum_{k_1+\cdots+k_m=n} \binom{n}{k_1,\dots,k_m}.$$

Or else we can imagine choosing first the $k_1$ places for the $a_1$'s. Then, from the remaining $n-k_1$ positions, we choose the $k_2$ places where the $a_2$'s will go, then from the remaining $n-k_1-k_2$ positions we choose the $k_3$ places where the $a_3$'s will go, and so on. This gives us a count of $$\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots \binom{n-k_1-\cdots-k_{n-1}}{k_m}.$$

Now use the fact that $\binom{q}{p}=\frac{q!}{p!(q-p)!}$ to express each of the above binomial coefficients in terms of factorials. There is dramatic cancellation, and we obtain $$\frac{n!}{k_1!k_2!\cdots k_m!}.$$ If the above (non-combinatorial) expression is the one used to define the multinomial coefficient, this way of counting the words gives us the desired result.

Comment: It is worthwhile to recast the argument in terms of distribution among bins, or distribution of presents to kids. It is very useful, for understanding and for teaching, to have concrete "stories" to accompany counting problems.

The presentation above would not be right in introducing the subject. First we need to have some concrete computations. The next step is to deal with something like $\sum \binom{n}{a,b,c}$ or $\sum \binom{n}{a,b,c,d}$. A too early introduction of subscripts tends to interfere with the understanding.

-

$m^n$ is the number of functions from $\{1,...,n\}$ to $\{1,...,m\}$.

An individual term on the left side is the number of ways of partitioning $\{1,..,n\}$ into an ordered sequence of sets $(P_1,P_2,...,P_m)$ where $|P_i|=k_i$. In particular, then, the sum of these terms is the number of ways of partitioning $\{1,...,n\}$ into an ordered sequence of $m$ sets.

Find a correspondence between the set of functions $f:\{1,...,n\}\rightarrow \{1,...,m\}$ and the set of partitions of $\{1,...,n\}$ into an ordered set of $m$ components.

[This partly depends on the way you defined $n\choose k_1,...,k_m$. If you defined it combinatorially, you are done. Otherwise, you have to prove that it is equal to the number of ways of partitioning $\{1,...,n\}$ as $(P_1,...,P_m)$ with $|P_i|=k_i$.]

-
+1. I was writing the answer when your answer got loaded and my answer was the same as yours. –  user17762 Oct 20 '11 at 19:18

Expand the product $(1+\dots+1)(1+\dots+1)\dots(1+\dots+1)$ of $n$ factors containing $m$ summands each.

Each term of the expansion is chosen by deciding in which sets of parentheses to choose the first one, in which set of parentheses to chose the second one and so on.

-

$m^n$ is the number of ways to put $n$ distinct marbles in to $m$ bags; that is, for each marble, there are $m$ bags into which it can go, so for $n$ marbles, there are $m^n$ possibilities.

Consider the number of ways to put $k_j$ marbles into bag $j$ for each $j$ from $1,2,\dots,m$ where $k_1+k_2+\dots+k_m=n$. There are $n!$ permutations of the $n$ marbles. In each permutation, consider the first $k_1$ to be in bag $1$, the next $k_2$ to be in bag $2$, and so on. Each way to fill the bags accounts for exactly $k_1!k_2!\dots k_m!$ (the number of ways to permute the marbles within each "bag") of the $n!$ permutations. Thus, there are $$\frac{n!}{k_1!k_2!\dots k_m!}\tag{1}$$ ways to put $k_j$ marbles into bag $j$ for each $j$ from $1,2,\dots,m$. So the number of ways to put $n$ marbles into $m$ bags is the sum of $(1)$ over all the posssibilities: $$\sum_{k_1+\dots+k_m=n}\frac{n!}{k_1!k_2!\dots k_m!}\tag{2}$$ Since $m^n$ and $(2)$ count the same thing, we have $$\sum_{k_1+\dots+k_m=n}\frac{n!}{k_1!k_2!\dots k_m!}=m^n$$

-