Higher Dimensional Rook Polynomials

Rook polynomials take their name from the chess piece rook, which only moves 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 xk corresponding to the number of ways of placing k non-attacking rooks. For example, the rook polynomial for the chess board is
r(x) = 40320 x8 + 322560 x7 + 564480 x6 + 376320 x5 + 117600 x4 + 18816 x3 + 1568 x3 + 64 x + 1.

It is possible to generalize the definition of rook polynomials to those boards which are three and higher dimensional. A three dimensional board will have rows, columns and towers. It will consist of cells which are stacked one above another. The rook polynomial of such a board will again be defined in the same way, where the coefficient rk in front of xk in the polynomial counts the number of ways of placing k rooks on the three (or higher) dimensional board.

The properties of two-dimensional rook polynomials generalize nicely to higher dimensional rook polynomials. There are families of two-dimensional boards whose rook numbers correspond with famous number sequences. It is also possible to generalize these boards to three and higher dimensions, and determine whether these generalized boards correspond with any number sequences.

Ferrers boards are a special type of boards in two-dimensions whose columns all share a fixed bottom line and the heights of the columns are non-decreasing. The rook polynomial for such a board enjoys a special property that it can be written as a product of linear factors depending on the column heights. Another possible research direction is to see whether there is a family of boards in higher dimensions which would serve as generalizations of Ferrers boards.

In fact, starting with any two-dimensional rook polynomial feature we can create a corresponding problem for higher-dimensional rook polynomials. This is a project that I am currently investigating with students.