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