Problem: For fixed $m,n\in\mathbb{N}$, find $$\sum_{k_1+\cdots+k_n=m}\frac{1}{k_1!\cdots k_n!}$$ where the sum is over all integers $k_i\geq 0$ such that $k_1+\cdots+k_n=m$.
I tried to come up with a series with the above coefficients, but I failed.
Asked
Active
Viewed 101 times
4
Orthogone
- 43
-
3Hint: Multinormial theorem – achille hui Jan 08 '15 at 20:09
-
Please don't accept answers so quickly. This will prevent people from adding other good answers, which would be useful to not just you, but future folks who have this question... – Aryabhata Jan 08 '15 at 20:48
2 Answers
10
The multinomial theorem says that $$ (x_1+x_2+\dots+x_n)^m=\sum_{k_1+\cdots+k_n=m}\frac{m!}{k_1!k_2!\cdots k_n!}x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n} $$ Therefore $$ (\overbrace{1+1+\dots+1}^{n\text{ ones}})^m=\sum_{k_1+\cdots+k_n=m}\frac{m!}{k_1!k_2!\cdots k_n!} $$ and so $$ \sum_{k_1+\cdots+k_n=m}\frac1{k_1!k_2!\cdots k_n!}=\frac{n^m}{m!} $$
robjohn
- 345,667
3
Using power series (which is what I presume you were trying to use?):
$$e^{nx} = \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} + \dots\right)^n $$
The coefficient of $x^m$ in the right side is your expression.
The left side is
$$e^{nx} = 1 + nx + \frac{(nx)^2}{2!} + \dots + \frac{(nx)^m}{m!} + \dots$$
The coefficient of $x^m$ is $$\frac{n^m}{m!}$$
Note: we used the power series for $e^x$.
Aryabhata
- 82,206
-
This approach can be used to prove binomial/multinomial theorem, if you so choose to... – Aryabhata Jan 08 '15 at 20:44
-