with one on each row, such that no rook attacks another rook.
- Boundary condition: 0 free rows on a board counts as one configuration.
- 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 free rows on an board:
| | | r(n-1, k-1)
| | | | BLANK
- : We fill out with rooks such that we have free rows. Then, we add the final row. Note that since we have rooks, free rows is equivalent to free columns! Now, we can't leave the final row free, since we have already exhausted our free rows in the recursion. We have free columns for the rook in the final row to inhabit. So we get .
§ Bijection between rooks and Stirling numbers of the second kind
Finally, note that , as
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 denotes a placement of wrooks on with
The corresponding "counting" object is called as the signless stirling numbers: