# Combinatorial proof of a Stirling number identity.

Consider the identity $$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$ where $${n\brace k}$$ is a Stirling number of the second kind. This is slightly reminiscent of the binomial identity $$\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$$ which essentially states that the number of even subsets of a set is equal to the number of odd subsets.

Now there is an easy proof of the binomial identity using symmetric differences to biject between even and odd subsets. I am wondering if there is an analogous combinatorial interpretation for the Stirling numbers. The term $$k!{n\brace k}$$ counts the number of set partitions of an $$n$$ element set into $$k$$ ordered parts. Perhaps there is something relating odd ordered partitions with even ordered partitions?

As an added note, there is a similar identity $$\sum_{k=1}^n(-1)^k(k-1)!{n\brace k}=0$$ for $$n \geq 2$$. A combinatorial interpretation of this one would also be appreciated.

• May inclusion exclusionn principle will help? Commented May 18, 2013 at 4:21

Perhaps there is something relating odd ordered partitions with even ordered partitions?

There is indeed. Let's try to construct an involution $T_n$, mapping odd ordered partitions of $n$-element set to even and vice versa: if partition has part $\{n\}$, move $n$ into previous part; otherwise move $n$ into new separate part.

Example: $(\{1,2\},\{\mathbf{5}\},\{3,4\})\leftrightarrow(\{1,2,\mathbf{5}\},\{3,4\})$.

This involution is not defined on partitions of the form $(\{n\},\ldots)$, but for these partitions one can use previous involution $T_{n-1}$ and so on.

Example: $(\{5\},\{4\},\{1,2\},\{\mathbf{3}\})\leftrightarrow(\{5\},\{4\},\{1,2,\mathbf{3}\})$.

In the end only partition without pair will be $(\{n\},\{n-1\},\ldots,\{1\})$. So our (recursively defined) involution gives a bijective proof of $\sum_{\text{k is even}}k!{n \brace k}=\sum_{\text{k is odd}}k!{n \brace k}\pm1$ (cf. 1, 2).

Upd. As for the second identity, the involution $T_n$ is already defined on all cyclically ordered partitions, so $\sum_{\text{k is even}}(k-1)!{n \brace k}=\sum_{\text{k is odd}}(k-1)!{n \brace k}$.

P.S. I can't resist adding that $k!{n \brace k}$ is the number of $(n-k)$-dimensional faces of an $n$-dimensional convex polytope, permutohedron (the convex hull of all vectors formed by permuting the coordinates of the vector $(0,1,2,\ldots,n)$). So $\sum(-1)^{n-k}k!{n \brace k}=1$ since it's the Euler characteristic of a convex polytope.

• much more combinatorial (+1)
– robjohn
Commented May 23, 2013 at 13:30
• Beautiful, thank you.
– EuYu
Commented May 23, 2013 at 18:12

For the sake of completeness I include a treatment using generating functions. The exponential generating function of the Stirling numbers of the second kind is $$G(z, u) = \exp(u(\exp(z)-1))$$ so that $${n \brace k} = n! [z^n] \frac{(\exp(z) - 1)^k}{k!}.$$ It follows that $$\sum_{k=0}^n (-1)^k k! {n \brace k} = n! [z^n] \sum_{k=0}^n (1-\exp(z))^k = n! [z^n] \sum_{k=0}^\infty (1-\exp(z))^k,$$ where the last equality occurs because the series for $(1-\exp(z))^k$ starts at degree $k.$ But this is just $$n! [z^n] \frac{1}{1-(1-\exp(z))} = n! [z^n] \exp(-z) = (-1)^n,$$ showing the result.

These are not combinatorial interpretations, but they are simple.

The defining equation for Stirling numbers of the second kind is $$\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{x}{k}k!=x^n\tag{1}$$ That is, Stirling numbers of the second kind tell how to write monomials as a combination of falling factorials (or combinatorial polynomials).

Noting that $\displaystyle\binom{-1}{k}=(-1)^k$ and setting $x=-1$ yields \begin{align} \sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^kk!= \sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{-1}{k}k!=(-1)^n \end{align}

Since $\displaystyle\binom{x}{k}=\binom{x-1}{k-1}\frac{x}{k}$ and $\begin{Bmatrix}n\\0\end{Bmatrix}=0$ for $n\ge1$, we can rewrite $(1)$ as $$\sum_{k=1}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{x-1}{k-1}(k-1)!=x^{n-1}\tag{2}$$ Setting $x=0$ yields $$\sum_{k=1}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{k-1}(k-1)!=0^{n-1}$$ where $0^0=1$ for the case $n=1$.

• Certainly the second part is supposing $n>0$, so that the term for $k=0$ can be dropped. However it fails to accommodate to the fact (even though some wish to deny it) that $0^0=1$. Stated more directly, it fails for $n=1$. Commented May 23, 2013 at 14:56
• @MarcvanLeeuwen: Good point. I got rid of the exponent when $n=1$ when I shouldn't have.
– robjohn
Commented May 23, 2013 at 15:54