Sum identity using Stirling numbers of the second kind

Question

Experimenting with series representations of $e^{x e^x}$ I came across the two seemingly different power series $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!}$$ and $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ They should be and are in fact identical. By equating the coefficients it is obvious that $$\sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!} = \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ Going through some values of $n$ reassures the correctness of the equation, however I have no idea how one could show this algebraically. An equivalent equation would be $$\sum_{k=0}^{n} {n \choose k} (n-k)^k = \sum_{k=0}^{n} {n \choose k} \sum_{i=0}^{k} {k \choose i} \sum_{j=1}^{i} (-1)^{i-j} {i \choose j} j^{k-i}\,,$$ which is obtained through multiplication of both sides by $n!$ and an explicit formula for the Stirling numbers. No matter what I try, I seem to run into a brick wall. How can I (algebraically) show that the equation is correct for arbitrary $n$?

Answer 1

Here is another variation of the theme. In order to prove the binomial identity \begin{align*} \sum_{k=0}^{n} \binom{n}{k} (n-k)^k =\sum_{k=0}^{n} \binom{n}{k} \sum_{i=0}^{k}\binom{k}{i} \sum_{j=0}^{i}\binom{i}{j} (-1)^{i-j} j^{k-i}\tag{1} \end{align*}

we take a look at a binomial inverse pair. Let $F(x)=\sum_{n=0}^\infty f_n \frac{x^n}{n!}$ and $G(x)=\sum_{n=0}^\infty g_n \frac{x^n}{n!}$ be exponential generating functions. We consider the following

Binomial inverse pair: \begin{align*} F(x)&=G(x)e^x&G(x)&=F(x)e^{-x}\\ f_n&=\sum_{k=0}^{n}\binom{n}{k}g_k&g_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}f_k\qquad \tag{2} \end{align*}

This simple one and many other examples of binomial inverse pairs can be found e.g. in the classic Combinatorial Identities by John Riordan ($1968$).

We obtain from (2) by successively substituting $f_n$ resp. $g_n$ \begin{align*} f_n&=\sum_{k=0}^{n}\binom{n}{k}g_k\tag{3}\\ &=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}f_i\\ &=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{i}\binom{i}{j}g_j\tag{4} \end{align*}

Setting $g_k=k^{n-k}$ we obtain from (3) and (4)

The following is valid for $n\geq 0$: \begin{align*} \sum_{k=0}^{n}\binom{n}{k}k^{n-k}=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}\sum_{j=0}^{i}\binom{i}{j}j^{i-j}\tag{5} \end{align*}

Observe the LHS of (5) corresponds to the LHS of (1) by replacing $k\rightarrow n-k$. So, we are nearly finished.

Finally we have to show the RHS of (5) is equal to the RHS of (1). Be careful, although they look similarly, they are not the same!

The validity of \begin{align*} \sum_{k=0}^{n} \binom{n}{k} \sum_{i=0}^{k}\binom{k}{i}\sum_{j=0}^{i}\binom{i}{j} (-1)^{i-j} j^{k-i} =\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^k\binom{k}{i}\sum_{j=0}^{i}\binom{i}{j}(-1)^{k-i}j^{i-j} \end{align*} is shown in this question and the claim follows.

Note: During analysis of the identity, when I had the association with binomial inverse pairs I was pretty sure, that the expressions (4) and (5) should already result in the RHS of (1). It was really amazing to see that this was not the case and it needed a considerable amount of effort to complete the answer.

Answer 2

Here is a combinatorial proof; it can probably be turned into an algebraic proof (in the sense of algebraic manipulation of sums) with some effort. The combinatorics will tell you what needs to be reindexed to get things to work out.

This is an exponential generating function, so a natural question is what sequence it's the exponential generating function of. The answer, which can be deduced from a suitable version of the exponential formula, is:

The coefficient of $\frac{x^n}{n!}$ in $e^{xe^x}$ counts the number of ways to partition a set $N$ with $n$ elements into nonempty subsets, then distinguish an element of each subset.

The LHS counts pairs consisting of a subset $K$ of $N$ and a function $K \to N \setminus K$. So we want to show this is in bijection with the above. The bijection turns out to be that $N \setminus K$ is the set of distinguished elements, and the preimages of the function $K \to N \setminus K$ give the rest of the partitions the distinguished elements are in.

The RHS counts tuples consisting of

• a subset $K$ of $N$,
• a subset $I$ of $K$,
• a partition of $K \setminus I$ into $|I|$ nonempty subsets, and
• a bijection between $I$ and the partitions of $K \setminus I$.

Again we want to show this is in bijection with the above. Here the bijection turns out to be that $N \setminus K$ is the set of distinguished elements such that the partition they're in has no other elements. All the other partitions have at least one other element, and the distinguished elements for those correspond to $I$, while the rest of the partitions correspond to the nonempty partitions of $K \setminus I$.

Answer 3

Suppose we seek an alternative representation of

$$\sum_{k=0}^n \frac{(n-k)^k}{(n-k)! \times k!}$$

in terms of Stirling numbers. We will use the species of set partitions which is

$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

which yields the generating function

$$G(z, u) = \exp(u(\exp(z)-1))$$

which in turn produces immediately that

$${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$

We start the computation by re-indexing to get

$$\sum_{k=0}^n \frac{k^{n-k}}{(n-k)! \times k!}.$$

Note that

$$k^{n-k} = (n-k)! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(kz) \; dz.$$

Therefore

$$\frac{k^{n-k}}{(n-k)!} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \exp(kz) \; dz.$$

Observe that this vanishes when $k\gt n$ (and it provides a value of zero for $k\gt n$ where $(n-k)!$ is not defined) so we have a built-in range enforcement and may extend the sum to infinity. We thus obtain

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k\ge 0} \frac{1}{k!} z^k \exp(kz) \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z\exp(z)) \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) \exp(z(\exp(z)-1)) \; dz.$$

Extracting coefficients now yields

$$\sum_{k=0}^n \frac{1}{(n-k)!} [z^k] \exp(z(\exp(z)-1)) \\ = \sum_{k=0}^n \frac{1}{(n-k)!} [z^k] \sum_{q=0}^\infty \frac{z^q}{q!} (\exp(z)-1)^q \\ = \sum_{k=0}^n \frac{1}{(n-k)!} \sum_{q=0}^k [z^{k-q}] \frac{1}{q!} (\exp(z)-1)^q \\ = \sum_{k=0}^n \frac{1}{(n-k)!} \sum_{q=0}^k \frac{1}{(k-q)!} {k-q\brace q}.$$

This is the claim.