A Universe of Sorts

§ Set partitions

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:

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

§ 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] \}

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:

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

§ 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)