$S(n, k) \equiv S(n-1, k-1) + kS(n-1, k)$

- For the $n$th element, I either build a new equivalence class $\{ n \}$and then make $k-1$ equivalence classes from $\{1\dots (n-1)\}$.
- Alternatively, I have $k$ equivalence classes from $\{1 \dots (n-1)\}$, say $P[1], P[2], \dots, P[k]$I decide into which $P[i]$ the $n$ should go, which gives me $k$ choices.
- Initial conditions: $S(0, 0) = 1$, $S(0, k \neq 0) = S(n \neq 0, 0) = 0$.

Interesting interpretation: The number of ways to surject an $n$ element set into a $k$ element set, since a surjection breaks a set up into a known number of fibers (in this case, $k$ fibers).This is not entirely true, because we only get $k$ equivalence classes of the set $\{1, \dots, n\}$. We need to decide where to map each equivalence class. So the correct count of $\{ [n] \xrightarrow{onto} [k] \}$ is $k!S(n, k)$: there are $k!$ ways to map equivalence classes of $n$ to elements of $k$

```
Delta(4):
+--+
| |
+--+--+
| | |
+--+--+--+
| | | |
+--+--+--+--+
```

Hopefully, this looks like a staircase with 4 stairs starting from the ground.
We have filled in squares of $[3, 2, 1]$ blocks stacked above one another.
We define $r(n, k)$ to be the number of legal rook placements on a board $\Delta(n)$
with $k$ free rows. That is, we have $(n-k)$ rooks to place on the board $\Delta(n)$,
with one on each row, such that no rook attacks another rook.
- Boundary condition: $r(0, 0) = 0$ 0 free rows on a $\Delta(0)$ board counts as one configuration.
- Recurrence: $r(n, k) \equiv r(n-1, k-1) + k r(n-1, k)$

- $r(n-1, k-1)$ term: We don't place a rook on the bottom row. This means we have used up a free row, and need to place rooks with $(k-1)$ free rows on an $(n-1)$ board:

```
+--+
| |
+--+--+
| | | r(n-1, k-1)
+--+--+--+
+--+--+--+
| | | | BLANK
+--+--+--+--+
```

- $k r(n-1, k)$: We fill out $\Delta(n-1)$ with rooks such that we have $k$ free rows. Then, we add the final row. Note that since we have rooks, $k$ free rows is equivalent to $k$ free columns! Now, we can't leave the final row free, since we have already exhausted our $k$ free rows in the recursion. We have $k$free columns for the rook in the final row to inhabit. So we get $k r(n-1, k)$.

$\begin{aligned}
&S(n, k) = S(n-1, k-1) + k S(n-1, k) \\
&r(n-k, k) =_? r(n-1 - (k-1), k-1) + k r(n-1 - k, k) \\
&r(n-k, k) =_? r(n-k, k-1) + k r(n-k-1, k) \\
&\text{set $m = n-k$: } \\
&r(m, k) = r(m, k-1) + k r(m, k) \\
\end{aligned}$

$\begin{aligned}
&w(n, k) \equiv \\
&~ w(n-1, k-1)~ \text{Leave bottom row free: uses up a free row} + \\
&~n w(n-1, k)~ \text{Place a wrook on bottom row: $n$ possible positions}
\end{aligned}$

The corresponding "counting" object is called as the signless stirling numbers:
TODO