# Is there a nice way to write the sum $\sum_{\sum k_i = m} \frac{1}{k_1! k_2! ... k_n!}$?

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.

• This is just defining the problem away, but writing $k=(k_1,\dots,k_n)$ as a multiindex rewrites this as the innocent-looking $\sum_{|k|=m} \frac1{k!}$ Commented Mar 3, 2018 at 16:20
• Not binomial. Multiply through by $m!$ to get the multinomial theorem. $n^m$ Commented Mar 3, 2018 at 16:21
• Oh right, of course. :) Commented Mar 3, 2018 at 16:22
• @ziggurism nice. thanks a bunch Commented Mar 3, 2018 at 16:24

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:

1. For all $k_i\ge 0$.
2. For all $k_i\ge 1$.

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.