Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.