# Proof that $\sum_{k=1}^n(-1)^k(k-1)!{n \brace k} = 0$ in use combinatoric interpretation

Proof that $$\\\sum_{k=1}^n(-1)^k(k-1)!{n \brace k} = 0\\$$ where $$n > 1$$. I know how it can be done with standard algebraic methods:

Solution

\begin{align*} \sum^n_{k=1}(-1)^k(k-1)!{n \brace k} &=\sum^n_{k=1}(-1)^k(k-1)!\left(k{n-1 \brace k} + {n-1 \brace k-1}\right) = \\ &=\sum^n_{k=1}(-1)^k k!{n-1 \brace k} + \sum^n_{k=1}(-1)^k (k-1)!{n-1 \brace k-1} \end{align*}

We can describe both sums: \begin{align*} &=&&- 1!{n-1 \brace 1} + 2!{n-1 \brace 2} - 3!{n-1 \brace 3} + \dots + (-1)^{n-1}(n-1)!{n-1 \brace n-1} + (-1)^{n}n!{n-1 \brace n} + \\ &&&- 0!{n-1 \brace 0} + 1!{n-1 \brace 1} - 2!{n-1 \brace 2} - \dots + (-1)^{n-1}(n-2)!{n-1 \brace n-2} + (-1)^{n}(n-1)!{n-1 \brace n-1}\\ \end{align*}

We see that elements of both sums reduce so we can write that as: $$= -0!{n-1 \brace 0} + (-1)^{n} \cdot n! \cdot {n-1 \brace n} = 1 \cdot [n-1 = 0] + (-1)^{n} \cdot n! \cdot 0 = 0 + 0 = 0$$
But I am really interested in combinatoric proof. I know that I should find bijection between even and odd elements, but I don't know how it can be done.

Thanks for showing the algebraic method. My answer below is inspired by it / an interpretation of it, and I wouldn't have succeeded without your equations. :)

Let $$[n] = \{1, 2, \dots, n\}$$ be the ground set.

• By definition, $${n \brace k} =$$ no. of ways to partition $$[n]$$ into a set of $$k$$ non-empty subsets.

• So $$k! {n \brace k} =$$ no. of ways to partition $$[n]$$ into a sequence of $$k$$ non-empty subsets. (Sequence means order of the subsets matter.)

• Further, $$(k-1)! {n \brace k} =$$ no. of ways to partition $$[n]$$ into a sequence of $$k$$ non-emtpy subsets, but where the subset containing a distinguished element, call it $$1$$, comes last. (Requiring it to come last means you can only permute the remaining $$(k-1)$$ subsets.)

For shorthand, define a foobar of length $$k$$ to be a way to partition $$[n]$$ into a sequence of $$k$$ non-empty subsets, where the subset containing $$1$$ comes last. Thus, $$(k-1)! {n \brace k} =$$ no. of foobars of length $$k$$.

Now consider all possible foobars, of any length. These come in two types: either the last subset is the singleton $$\{1\}$$, or it contains some other element besides $$1$$. The two types of foobars are in bijection:

$$(S_1, S_2, \dots, S_k, \{1\}) \iff (S_1, S_2, \dots, S_k \cup \{1\})$$

In each such pair, one foobar has odd length and the other foobar has even length. Therefore, the no. of even-length foobars $$=$$ the no. of odd-length foobars, which is exactly the formula we are trying to prove. $$\square$$

Why this is an interpretation of your algebraic method: In your recurrence $${n \brace k} = k {n-1 \brace k} + {n-1 \brace k-1}$$, the second term counts cases where $$1$$ is by itself, and the first term counts cases where $$1$$ is in a subset with other element. And then you showed that this $$2$$-way classification leads to lots of cancellations, so I simply had to find a bijection that relies on this classification.