Rook polynomials take their name from the chess piece rook, which attacks horizontally along the rows, or vertically along the columns. The picture on the right shows a placement of 8 rooks on the regular chess board in such a way that no rook can attack another (the colors of the rooks are irrelevant). The coefficients of the rook polynomial for a board gives the number of ways of placing the non-attacking rooks on the board, with the coefficient of x^k corresponding to the number of ways of placing k non-attacking rooks. For example, the rook polynomial for the regular chess board is
r(x) = 40320 x⁸ + 322560 x⁷ + 564480 x⁶ + 376320 x⁵ + 117600 x⁴ + 18816 x³ + 1568 x³ + 64 x + 1.
But in this project our boards will be more general than the regular chess board. In two dimensions our boards will be tiles labeled with (i, j) where i and j are integers between 1 and m, and 1 and n, respectively. In this case the board is a subset of the rectangle board of size mxn.

A curious question is: What happens if the rooks can fly? Is it possible to generalize the theory to "boards" in three and higher dimensions? A three dimensional board will be one with rows, columns and towers. Let's say that the board is made up of cell that are stacked one above another. We can define the rook polynomial of such a board in the same way, where the coefficient r_k in front of x^k in the polynomial counts the number of ways of placing k non-attacking rooks on the three (or higher) dimensional board. But the question is how do we want the rooks to attack in three and higher dimensions? A student and I decided that rooks would attack along planes in three dimensions, and in hyperplanes in higher dimensions [1]. It is also possible to continue letting rooks attack along lines, or let rooks attack along k-dimensional subspaces where k is less than the dimension of the space we are in. But in this project we will consider the case where rooks attack along subspaces with one less dimension than the space the rooks are in.

The properties of two-dimensional rook polynomials generalize nicely to higher dimensional rook polynomials [1]. For example, the formulas for computing rook polynomials of larger boards using subboards either immediately generalizes or generalizes with slight modifications. Similarly, the formula which relates the rook polynomials of two complementary boards again generalizes with slight modification. In two dimensions, there are families of boards whose rook numbers correspond to famous number sequences. A natural question then is whether it is possible to generalize these boards to three and higher dimensions so that the higher dimensional rook numbers correspond to any interesting number sequences. We have some such boards and sequences in [1], with examples of two such boards, triangle and Genocchi boards, both of size 5, shown on the right. These boards have rook numbers corresponding to the central factorial and Genocchi numbers, respectively.

There is also a nice relation between two-dimensional rook polynomials and matchings in graph theory. A matching in a graph is a collection of edges which do not share endpoints, as in the picture to the right. We imagine this graph to correspond to a rook board where the rows are labeled with the top vertices and the columns with the bottom vertices. We place a tile at the intersection of a row and a column if there is an edge between the corresponding vertices in the graph. Then each edge selected in the matching corresponds to a rook placement in the corresponding tile. Since the edges do not share endpoints, the rooks corresponding to them form a non-attacking rook arrangement. In the REU, we will be investigating higher dimensional rook theory questions from this graph theory perspective.