prove $\sum_{k=0}^n(-1)^k k!S_k^n = (-1)^n $

Question

Question:

Let $S_k^n$ denote the Stirling number of the second kind and let n and k be positive integers. Prove that:

$\sum_{k=0}^n(-1)^k k!S_k^n = (-1)^n $

Can you give a combinatorial interpretation?

induction:

so i was thinking that $k!S_k^n$ is the number of functions $A\rightarrow B$ where $|A|=n$ and $|B|=k$ so this statement could have a combinatorial interpretation but we can't count something $-1$ so it doesn't make sense, is this statement even true?

Answer 1

Using the species

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

for labeled set partitions we have the generating function

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

so that

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

We get for the sum

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

The last equality is because

$$1-\exp(z) = - z - \frac{1}{2} z^2 - \frac{1}{6} z^3 - \cdots$$

and

$$\exp(-z)-1 = -z + \frac{1}{2} z^2 - \frac{1}{6} z^3 + \cdots$$

and we are extracting the coefficient on $[z^n]$ from a formal power series that starts at $z^{n+1}.$

Answer 2

$S_k^n = {n \brace k}$ is the number of ways for partitioning a set with $n$ elements in $k$ parts. That leads to$${n+1\brace k}=k{n\brace k}+{n\brace k-1}\tag{1}$$ hence by setting $$ A_n = \sum_{k=0}^{n}(-1)^k k!{n \brace k} \tag{2} $$ we have $A_0=1$ by direct computation and $$\begin{eqnarray*} A_{n+1}&=&\sum_{k=0}^{n+1}(-1)^k k!{n+1\brace k}\\&=&1+(-1)^{n+1}(n+1)!+\sum_{k=1}^{n}(-1)^k k!{n\brace k-1}+\sum_{k=1}^{n}(-1)^k k\cdot k!{n\brace k}\\&=&1+(-1)^{n+1}(n+1)!-\sum_{k=0}^{n-1}(-1)^k (k+1)!{n\brace k}+\sum_{k=1}^{n}(-1)^k k\cdot k!{n\brace k}\\&=&-\sum_{k=0}^{n}(-1)^k\left((k+1)!-k\cdot k!\right){n\brace k}\\&=&-\sum_{k=0}^{n}(-1)^k k!{n\brace k}=-A_n\tag{3}\end{eqnarray*}$$ from which $A_n=(-1)^n$ follows by induction.
Another approach comes from recalling that, by the inclusion-exclusion principle,$$(-1)^k k!{n\brace k}=\sum_{j=0}^{k}(-1)^j\binom{k}{j}j^n $$ hence $$\sum_{k=0}^{n}(-1)^k k! {n\brace k}=\sum_{j=0}^{n}(-1)^j j^n \sum_{k\geq j}\binom{k}{j}=\sum_{j=0}^{n}(-1)^j j^n\binom{n+1}{j+1}.$$ The algebraic identity $$ \sum_{k=0}^{n}{n\brace k}(x)_k = x^n\tag{4} $$ where $(x)_k = x(x-1)\cdots(x+1-k)$ is a way for counting the functions from $[1,n]$ to $[1,x]$ (according to the cardinality of their range) if $x\in\mathbb{N}^+$. But it holds also for non-positive values of $x$, like, for instance $x=-1$, where it gives our identity $A_n=(-1)^n$.