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.
 A: 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.
