Stirling numbers of second type

Question

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}$$

Answer 1

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