Let $X$ be a set. A breakup of $X$ into pairwise disjoint sets $A[i]$ such that $\cup_i A[i] = X$ is called a partition $P$ of the set $X$.

§ Stirling numbers of the second kind: $S(n, k)$

These count the number of ways to break an $n$ element set into $k$ partitions/equivalence classes.

The recurrence is:

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

§ Stirling numbers and surjections

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$

§ Rook theory(!)

Turns out we can provide a crazy relationship betweeen ferrers diagrams, and rooks (as in the chess piece) and stirling numbers of the second kind.

We define $\Delta(n)$ to be the board consisting of the integer partition $[n-1, n-2, \dots, 1]$. For example, we think of $\Delta(4)$ as:

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

§ Bijection between rooks and Stirling numbers of the second kind

Finally, note that $S(n, k) = r(n-k, k)$, as $S(n, k) = S(n-1, k-1) + k S(n-1, k)$ which is equivalent to asking:

§ Directly reading off the bijection between set partitions and rook placements

I found this very cool. The idea is to treat each rook as a "bouncer" that bounces light rays. All elements hit by a light ray belong to an equivalence class.

§ Wrooks and signless stirling numbers

Similar to the rooks, we define a wrook (a weak rook) as one that only attacks on its row. Here $w(n, k)$ denotes a placement of wrooks on $\Delta(n)$ with $k$ free rows.

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

TODO