4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Hint: Multinormial theorem $\endgroup$ – achille hui Jan 8 '15 at 20:09
  • $\begingroup$ 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... $\endgroup$ – Aryabhata Jan 8 '15 at 20:48
10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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