I have to give a combinatorial proof and the meaning of the following identity.
$$\sum_{k = 1}^n (-1)^k k !S(n,k) = (-1)^n,$$ where $S(n,k)$ is the Stirling number of the second kind.
Could anyone give me a hint on how to go about this? I suspect it has something to do with surjective maps, since I know that $k!S(n,k)$ is the number of bijective maps from $n$ to $k$.
Let $n$ be odd. The number of ways to partition $n$ elements into an odd number of sets is $1$ more than the number of ways to partition the elements into an even number of sets.
Proof idea: for each partitioning of $n$ into an even number of sets, find the smallest non-singleton set, and split it into two sets at the smallest element. This forms a bijection between the even number sets and the odd number sets, except for the (odd) partitioning consisting of all $n$ elements. A similar argument holds if $n$ is even.