4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

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