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.