Alternating sum of Stirling numbers equals 0

Question

How can I prove that the following formula is true for Stirling numbers of first kind.

For any $n \geq 2$, we have

$$\sum_{k=1}^n(-1)^k\left[\begin{matrix} n\\k\end{matrix}\right] =0$$

Actually I want to prove that the number of permutations of $\left\{1,2,\ldots,n\right\}$ with an even number of cycles equals the number of permutations of $\left\{1,2,\ldots,n\right\}$ with an odd number of cycles. This is equivalent to the above identity by the combinatorial interpretation of Stirling numbers.

Answer 1

Note that you have to assume that $n \geq 2$: when $n = 1$, the sum equals $-1$.

Combinatorial proof

It's enough to find a bijection on permutations which changes the parity of the number of cycles. One possibility is the following. Write a permutation as a product of cycles. If $1$ and $2$ belong to the same cycle $(1\alpha 2\beta)$, replace it with two cycles $(1\alpha)(2\beta)$; and vice versa. For example, here is the bijection for $S_4$: $$ (1)(2)(3)(4) \leftrightarrow (12)(3)(4) \\ (1)(2)(34) \leftrightarrow (12)(34) \\ (13)(2)(4) \leftrightarrow (132)(4) \\ (14)(2)(3) \leftrightarrow (142)(3) \\ (134)(2) \leftrightarrow (1342) \\ (143)(2) \leftrightarrow (1432) \\ (1)(23)(4) \leftrightarrow (123)(4) \\ (1)(24)(3) \leftrightarrow (124)(3) \\ (1)(234) \leftrightarrow (1234) \\ (1)(243) \leftrightarrow(1243) \\ (13)(24) \leftrightarrow (1324) \\ (14)(23) \leftrightarrow (1423) $$

Inductive proof

Another option is to use the formula $$ \newcommand{\stirling}[2]{\left[{#1 \atop #2}\right]} \stirling{n+1}{k} = n\stirling{n}{k} + \stirling{n}{k-1}. $$ When $n=2$ the claim is true by inspection. Suppose now that it holds for some $n$. Then $$ \begin{align*} \sum_{k=1}^{n+1} (-1)^k \stirling{n+1}{k} &= n\sum_{k=1}^n (-1)^k \stirling{n}{k} + \sum_{k=2}^{n+1} (-1)^k \stirling{n}{k-1} \\ &= n\sum_{k=1}^n (-1)^k \stirling{n}{k} - \sum_{k=1}^n (-1)^k \stirling{n}{k} \\ &= 0. \end{align*} $$

Answer 2

Here is an algebraic proof. The combinatorial species of permutations with cycles marked is given by $$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z}))$$ which yields the generating function $$G(z,u) = \exp\left(u\log\frac{1}{1-z}\right).$$ This immediately produces $$\left[ n\atop k\right] = n! [z^n] \frac{1}{k!}\left(\log\frac{1}{1-z}\right)^k.$$ Substitute this into the sum to get $$n! [z^n] \sum_{k=1}^n \frac{(-1)^k}{k!}\left(\log\frac{1}{1-z}\right)^k.$$ Supposing we have $n\ge 1$ we may extend the lower limit to include zero and the upper limit to infinity because $\log\frac{1}{1-z}$ starts at $z.$ This gives $$n! [z^n] \sum_{k=0}^\infty \frac{(-1)^k}{k!}\left(\log\frac{1}{1-z}\right)^k.$$ Simplify to obtain $$n! [z^n] \exp\left(-\log\frac{1}{1-z}\right) = n! [z^n] (1-z).$$ We assumed that $n\ge 1$ so this gives minus one for $n=1$ and zero otherwise. Indeed there is one permutation on $1$ element and it consists of a single odd cycle.