Stirling Numbers of the Second Kind and Nonattacking Rooks

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

The number of possible configurations of nonattacking rooks on a triangular chessboard can be counted by the Stirling numbers of the second kind . In particular, for rooks on a board with side length , the number of configurations is .

Contributed by: Robert Dickau (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Snapshot 1: there is only one configuration of nonattacking rooks on a triangle board with side —along the diagonal—which corresponds to the relation

Snapshot 2: a single rook on a board with side can be placed on any of the squares, so that

Snapshot 3: valid configurations can be derived recursively: the configurations for rooks on a board with side can be constructed from a combination of rooks on a board with side (adding an empty column to each existing configuration) and rooks on a board with side (adding a column with one rook in each valid square), which corresponds to the recurrence relation

Reference

[1] M. B. Wells, Elements of Combinatorial Computing, Oxford: Pergamon Press, 1971 p. 185.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send