# Combinatorial proof. What is this question asking?

Show for sums over all $i_1 + i_2 + \ldots + i_k = n, i_j \geq 0$, that $$\sum P(n;i_1,i_2,\ldots,i_k) = k^n$$

What is the index? I'm not even sure how to expand the LHS.

Update: $P$ is permutation. If the downvote was because there was something unclear, please let me know.

-
Presumably it's the sum over all $k$-tuples of nonnegative integers $(i_1,\ldots,i_k)$ with $i_1 + \ldots + i_k = n$. But what is $P$? – Robert Israel Feb 12 '13 at 0:01
I think it's the multinomial coefficient $\binom{n}{i_1,\ldots,i_k}$. – Douglas S. Stones Feb 12 '13 at 0:08
@DouglasS.Stones Yeah, I knew that, but I didn't know what was being indexed. At least it wasn't apparent to me. – AlanH Feb 12 '13 at 0:57
@AlanH: I believe that Brian M. Scott's answer does contribute to the community, so at the moment I am not going to delete this question. – Eric Naslund Feb 14 '13 at 23:54

## 1 Answer

I had to expand it to make it readable, but the summation can be written like this:

$$\large\sum_{i_1+\ldots+i_k=n\atop{i_1,\dots,i_k\ge 0}}P(n;i_1,i_2,\dots,i_k)\;.$$

Alternatively, it’s

$$\sum\left\{P(n:i_1,i_2,\dots,i_k):\sum_{j=1}^ki_j=n\text{ and }i_1,\dots,i_k\ge 0\right\}\;.$$

I can’t be sure of helping with the proof, though, until you tell us what $P(n;i_1,i_2,\dots,i_k)$ is. I’m going to guess that it’s the number of distinguishable permutations of a set of $n$ objects of $k$ types, $i_j$ being the number of indistinguishable objects of type $j$ for $j=1,\dots,k$. That makes your theorem a special case of the multinomial theorem.

Count the functions from $\{1,\dots,n\}$ to $\{1,\dots,k\}$ in two ways. You can think of such a function as an assigment of labels $1,\dots,k$ to the integers $1,\dots,n$. The term $P(n;i_1,\dots,i_k)$ is the number of ways to assign $i_1$ labels $1$, $i_2$ labels $2$, ..., and $i_k$ labels $k$.

-