I've encountered rook polynomials. I just can't seem to understand how to generate them by hand for small examples such as 3x3 boards.

Take for instance:

$$\begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ \end{matrix}$$

where $0$ means occupied.

I'd appreciate a guide or at least a suitable literature, where it's explained. Thanks.

  • $\begingroup$ What do you mean by "0 means occupied" here? There's a rook polynomial associated to each $m \times n$ rectangle, so for instance there is the rook polynomial of a $3 \times 3$ square, which is $6 x^3 + 18 x^2 + 9x + 1$. They're not associated to particular configurations. Also, if we're to assume that the 0's represent rooks above, then this isn't a valid configuration of rooks, because the rook in the lower-right corner attacks both of the other two (and vice-versa). $\endgroup$ – Daniel McLaury Dec 3 '14 at 21:02
  • $\begingroup$ @DanielMcLaury Well I should rephrase my question. $0$ means that the place cannot be occupied by a rook, only the places with a $1$ can be occupied. $\endgroup$ – David Dec 3 '14 at 21:43
  • $\begingroup$ Well, then that would be an extension of what's usually called a rook polynomial. It doesn't matter in this case, but you'd also need to clarify what the "occupied" states mean: does it mimic the rules of chess, where they block the rooks from attacking each other? $\endgroup$ – Daniel McLaury Dec 3 '14 at 21:49
  • $\begingroup$ @DanielMcLaury Well basically everything is the same, the rules and the rook moves, they are just on a different board. On a board that looks like the zero's and one's except 1's are squares(part of the board) and the 0's are blank spaces, places where rooks cannot be put. So just the board is modified. $\endgroup$ – David Dec 3 '14 at 21:53
  • $\begingroup$ If the board looks like 1010101, can I place four rooks, or just 1? $\endgroup$ – Daniel McLaury Dec 3 '14 at 21:54

For the board that's given, the rook polynomial would be $R(x)=1+6x+7x^2+x^3$,

since the coefficient of $x^n$ is the number of ways to place n non-attacking rooks on the board.

In addition to direct counting, the rook polynomial can be found by selecting a specific position, such as the third 1 in row 2, and using that

the rook polynomial with this place deleted is $r_1(x)=1+5x+4x^2$, and

the rook polynomial with this row and column deleted is $r_2(x)=1+3x+x^2$;

so the rook polynomial for the board is given by


A good reference for this topic is Alan Tucker's "Applied Combinatorics".

  • $\begingroup$ why is the coeffiecient at $x$ only 3? There are 6 places, so why only 3? $\endgroup$ – David Dec 3 '14 at 21:41
  • $\begingroup$ @user84413, I don't see how you're getting those coefficients. $\endgroup$ – Daniel McLaury Dec 3 '14 at 21:50
  • $\begingroup$ @DanielMcLaury I think I misinterpreted the problem; I thought that the 0's were the only places rooks were allowed, so I will try to correct my answer. $\endgroup$ – user84413 Dec 4 '14 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.