Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there any nice way to write $$\sum_{\sum k_i = m} \frac{1}{k_1! k_2! ... k_n!}$$
where $m$ and the $k_i$ are positive integers and $n$ is a fixed positive integer? I thought maybe multiplying by $m!$ and trying to get to a binomial sum, but I'm not sure.
This comes up in dealing with independent trials from a poisson distribution, namely when working with the statistic which sums the values of the trials.
Note that our primary tool here will be the series expansion:
$$e^x=\sum_{k\ge 0}\frac{1}{k!}x^k\tag{1}$$
Then let us consider the sum
$$\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}$$
for two distinct cases:
Case 1: $k_i\ge 0$
We see, by raising $(1)$ to the power $n$, that
$$(e^{x})^n=\sum_{m\ge 0}\left(\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}\right)x^m\, ,$$
and thus taking the $x^m$ coefficient:
$$[x^m]e^{nx}=\frac{n^m}{m!}=\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}\tag{Answer 1}$$
Case 2: $k_i\ge 1$
We want to do something similar to case 1 but avoiding $k$ values of $0$, hence consider the modification of $(1)$:
$$e^x-1=\sum_{k\ge 1}\frac{1}{k!}x^k\tag{2}$$
and raising $(2)$ to power $n$
$$(e^x-1)^n=\sum_{m\ge n}\left(\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}\right)x^m$$
then taking the coefficient of $x^m$
$$[x^m](e^x-1)^n=\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}\, .$$
We can write $(e^x-1)^n$ using the binomial expansion
$$(e^x-1)^n=\sum_{j=0}^{n} \binom{n}{j}(-1)^{n-j}e^{jx},$$
and therefore
$$[x^m](e^x-1)^n=\sum_{j=0}^{n}\binom{n}{j}(-1)^{n-j}[x^m]e^{jx}$$
$$\implies [x^m](e^x-1)^n=\sum_{j=0}^{n}\binom{n}{j}(-1)^{n-j}\frac{j^m}{m!}\, .$$
So, we have:
$$\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}=\frac{1}{m!}\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^m\, .$$
This is related to the Stirling numbers of the second kind:
$${m\brace n}=\frac{1}{n!}\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}j^m$$
by
$$\sum_{\sum k_i=m}\frac{1}{k_1!\cdots k_n!}=\frac{n!}{m!}{m\brace n}\tag{Answer 2}$$
The Multinomial Theorem says, $$ \sum_{\sum\limits_{i=1}^nk_i=m}\frac{m!}{k_1!\,k_2!\,\dots\,k_n!}1^{k_1+k_2+\cdots+k_n}=(\overbrace{1+1+\cdots+1}^{n\text{ copies}})^m\tag1 $$ Therefore, $$ \bbox[5px,border:2px solid #C0A000]{\sum_{\sum\limits_{i=1}^nk_i=m}^{\vphantom{1}}\frac1{k_1!\,k_2!\,\dots\,k_n!}=\frac{n^m}{m!}}\tag2 $$ Note that if we add $(2)$ for all $m\ge0$, we get $e^n$ which makes sense because the sum then allows all $k_1,k_2,\dots,k_n$ giving $$ \left(\sum_{k=0}^\infty\frac1{k!}\right)^n\tag3 $$
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k_{1} = 0}^{\infty}\ldots\sum_{k_{1} = 0}^{\infty} {1 \over k_{1}!\cdots k_{n}!}\,\bracks{z^{m}}z^{k_{1} + \cdots + k_{n}} = \bracks{z^{m}}\pars{\sum_{k = 0}^{\infty}{z^{k} \over k!}}^{n} = \bracks{z^{m}}\pars{\expo{z}}^{n} = \bracks{z^{m}}\expo{nz} = \bbx{n^{m} \over m!} \end{align}
Combinatorial interpretation: the fraction $\frac{m!}{k_1!\cdots k_n!}$ is the number of ways to partition $m$ distinct balls to $n$ distinct cells so that the $i$-th cell gets $k_i$ balls.
Summing this over all $k_1,\ldots,k_n$ we get the number of all surjections $\{1,\ldots,m\}\rightarrow\{1,\ldots,n\}$, i.e. $n!{m\brace n}$. Dividing back by $m!$, we get the answer.
