Stirling numbers of second type How can I do a combinatoric proof that for Stirling number of second type the equality if true:
$${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
 A: I will denote ${n \brace k}$ as $S(n,k)$ for simplicity.
To prove this, we will count the number, $N$, of onto functions $f$ from the set $S_1 = \{1, 2, \cdots, n\}$ to $S_2 = \{ 1, 2, \cdots, k \}$ in two ways.  
First count. We will express this in terms of $S(n,k)$.  To do so, we partition $S_1$ into $k$ disjoint parts $P_i$ and let $f(x) = i$ for all $x \in P_i$.  By definition, this can be done in $S(n,k)$ ways.  But we can permute the $k$ partitions $P_i$, which gives us the following result:
$$
N = k! \cdot S(n,k)
$$

Second count. To count this another way, we will employ the principle of inclusion-exclusion, which states the following.  
Principle of inclusion-exclusion. Let $\{S_j : 1 \leq j \leq n \}$ be a collection of sets.  Then
$$
\left | \bigcup_{j = 1}^{n} S_j \right | = \sum_{k = 1}^{n} \left [ (-1)^{k+1} \left ( \sum_{1 \leq j_1 < \cdots < j_k \leq n} | S_{j1} \cap \cdots \cap S_{jk} | \right ) \right ]
$$

Let $X$ be the set of all functions $f: S_1 \to S_2$.  Then it is clear that $|X| = k^n$, since for each of the $n$ elements in $S_1$, we have $k$ choices.  Now, for each $j$ such that $1 \leq j \leq k$, let 
$$
X_j = \{ f: S_1 \to S_2 \text{ such that } f \text{ does not have } j \text{ in its range }\}.
$$ 
Since we want to count $N$, the number of onto functions (that is, functions with all elements of $S_2$ in their ranges), 
$$ 
N = \left | \bigcap_{j = 1}^{k} (X - X_j) \right | = \left | X - \bigcup_{j = 1}^{k} X_j \right | = k^n - \left | \bigcup_{j = 1}^{k} X_j \right |
$$
By an argument similar to before, we have $|X_j| = (k-1)^n$ and
$$
\sum_{1 \leq i_1 < \cdots < i_j \leq k} |X_{i_1} \cap X_{i_2} \cap \cdots \cap X_{i_j} |= \binom{k}{j} (k-j)^n.
$$
Finally, by the principle of inclusion exclusion, we have
$$
N = k^n - \left ( \sum_{j = 1}^{k} (-1)^{j+1} \binom{k}{j} (k-j)^n \right )
$$
$$
= \sum_{j = 0}^{k} (-1)^j \binom{k}{j} (k-j)^n
$$

Finally, equating our two expressions for $N$, we obtain
$$
k! \cdot S(n,k) = \sum_{j = 0}^{k} (-1)^j \binom{k}{j} (k-j)^n
$$
which is equivalent to 
$$
\boxed{\displaystyle S(n,k) = \frac{1}{k!} \sum_{j = 0}^{k} (-1)^j \binom{k}{j} (k-j)^n}.
$$
