Where can I find a proof, that $s(n+1,k+1) = \sum_{i = 0}^{n} \binom{i}{k}s(n,i)$? In our Combinatorics Script it is written, that 
$$s_{n+1,k+1} = \sum_{i = 0}^{n} \binom{i}{k}s_{n,i}$$ for $n,k \in \mathbb{N}$.
The problem is that I can't find a combinatorial proof for that, not in the Script and not online. 
I thought about looking at a set $S_{n,k}$ of the permutations of $[n]$, which are the products of exactly $k$ disjoint cycles, but that's just a thought...
The Stirling numbers of the first kind are defined recursively by:

And how can one give a bijection between a set of the cardinality $\sum_{i=0}^{n} \binom{i}{k} s_{n,i}$ and $S_{n+1, k+1}$?
Apparently defining such a transformation can be extracted from the following example. Does someone know how it's done?
$(1,3,8,7)(2,9,5)(4,12,10,6)(11,13) \to (14,4,12,10,6,1,3,8,7)(2,9,5)(11,13)$
 A: You know what method works (almost) always to prove an identity about a sequence defined inductively? Induction.
Base case is trivial.
$$ s_{n+1,k+1}=s_{n,k}+ns_{n,k+1}= \sum_{i = 0}^{n-1} \binom{i}{k-1}s_{n-1,i}+ n\sum_{i = 0}^{n-1} \binom{i}{k}s_{n-1,i}$$$$= \sum_{i = 0}^{n-1} (\binom{i}{k-1}s_{n-1,i}+ \binom{i}{k}s_{n-1,i}) +(n-1)\sum_{i = 0}^{n-1} \binom{i}{k}s_{n-1,i}$$$$=\sum_{i = 0}^{n-1} \binom{i+1}{k}s_{n-1,i} +(n-1)\sum_{i = 0}^{n-1} \binom{i}{k}s_{n-1,i}$$$$=\sum_{i = 1}^{n} \binom{i}{k}s_{n-1,i-1} +(n-1)\sum_{i = 0}^{n-1} \binom{i}{k}s_{n-1,i}$$$$=\sum_{i = 0}^{n-1} \binom{i}{k}s_{n,i}+\binom{n}{k}=\sum_{i = 0}^{n} \binom{i}{k}s_{n,i}$$
$\blacksquare$
A: Let $A=\{a_1,\cdots,a_m \} $ be a finite set, that does not contain the element $n+1$. We begin by noting a one to one correspondence between permutations of this set and the conjugacy class of $A \cup \{n+1 \}$.
Given an element $\pi \in S_A$ ($\pi(a_i)=\pi_{a_i}$) we form an element of $S_{A \cup \{n+1 \}}$ by
\begin{eqnarray*}
\pi \rightarrow (n+1,\pi_{a_1}, \cdots , \pi_{a_m} ).
\end{eqnarray*}
We shall now use this to establish the following formula
\begin{eqnarray*}
\sum_{i=k}^{n}  {n \brack i} \binom{i}{k}  = {n+1 \brack k+1}.
\end{eqnarray*}
Let $ \sigma$ be an element of $S_n$ with $i$ cycles. Choose $k$ of these cycles and let $A$ be the set of elements in the other $i-k$ cycles. Now form an element of $S_{n+1}$ consisting of the $k$ chosen cycles and a cycle formed by the correspondence $S_A \rightarrow  S_{A \cup \{n+1 \}}$ defined above. Now let $k$ vary over its admissable values and the formula is proven.
