29
$\begingroup$

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$$ A combinatorial interpretation of this one would also be appreciated.

$\endgroup$
  • $\begingroup$ May inclusion exclusionn principle will help? $\endgroup$ – Norbert May 18 '13 at 4:21
22
+150
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ much more combinatorial (+1) $\endgroup$ – robjohn May 23 '13 at 13:30
  • $\begingroup$ Beautiful, thank you. $\endgroup$ – EuYu May 23 '13 at 18:12
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen May 23 '13 at 14:56
  • $\begingroup$ @MarcvanLeeuwen: Good point. I got rid of the exponent when $n=1$ when I shouldn't have. $\endgroup$ – robjohn May 23 '13 at 15:54
2
$\begingroup$

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.

$\endgroup$

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.