§ Set partitions

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

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

These count the number of ways to break an nn element set into kk partitions/equivalence classes. The recurrence is:
S(n,k)S(n1,k1)+kS(n1,k) S(n, k) \equiv S(n-1, k-1) + kS(n-1, k)
  • For the nnth element, I either build a new equivalence class {n}\{ n \}and then make k1k-1 equivalence classes from {1(n1)}\{1\dots (n-1)\}.
  • Alternatively, I have kk equivalence classes from {1(n1)}\{1 \dots (n-1)\}, say P[1],P[2],,P[k]P[1], P[2], \dots, P[k]I decide into which P[i]P[i] the nn should go, which gives me kk choices.
  • Initial conditions: S(0,0)=1S(0, 0) = 1, S(0,k0)=S(n0,0)=0S(0, k \neq 0) = S(n \neq 0, 0) = 0.

§ Stirling numbers and surjections

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

§ 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 Δ(n)\Delta(n) to be the board consisting of the integer partition [n1,n2,,1][n-1, n-2, \dots, 1]. For example, we think of Δ(4)\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][3, 2, 1] blocks stacked above one another. We define r(n,k)r(n, k) to be the number of legal rook placements on a board Δ(n)\Delta(n) with kk free rows. That is, we have (nk)(n-k) rooks to place on the board Δ(n)\Delta(n), with one on each row, such that no rook attacks another rook.
  • Boundary condition: r(0,0)=0r(0, 0) = 0 0 free rows on a Δ(0)\Delta(0) board counts as one configuration.
  • Recurrence: r(n,k)r(n1,k1)+kr(n1,k)r(n, k) \equiv r(n-1, k-1) + k r(n-1, k)
  • r(n1,k1)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 (k1)(k-1) free rows on an (n1)(n-1) board:
+--+
|  |
+--+--+
|  |  |  r(n-1, k-1)
+--+--+--+

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

§ Bijection between rooks and Stirling numbers of the second kind

Finally, note that S(n,k)=r(nk,k)S(n, k) = r(n-k, k), as S(n,k)=S(n1,k1)+kS(n1,k)S(n, k) = S(n-1, k-1) + k S(n-1, k) which is equivalent to asking:
S(n,k)=S(n1,k1)+kS(n1,k)r(nk,k)=?r(n1(k1),k1)+kr(n1k,k)r(nk,k)=?r(nk,k1)+kr(nk1,k)set m=nkr(m,k)=r(m,k1)+kr(m,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}

§ 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)w(n, k) denotes a placement of wrooks on Δ(n)\Delta(n) with kk free rows.
w(n,k) w(n1,k1) Leave bottom row free: uses up a free row+ nw(n1,k) Place a wrook on bottom row: n possible positions \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