# Find $\sum_{k_1+\cdots+k_n=m}\frac{1}{k_1!\cdots k_n!}$.

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.

• Hint: Multinormial theorem – achille hui Jan 8 '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 8 '15 at 20:48

## 2 Answers

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!}$$

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

• This approach can be used to prove binomial/multinomial theorem, if you so choose to... – Aryabhata Jan 8 '15 at 20:44
• Nice approach (+1) – robjohn Jan 8 '15 at 21:13