Rook polynomial

Despite its name, the rook polynomial is used not only to solve chess recreational problems but also in a number of problems arising in combinatorial mathematics, group theory, and number theory.

The coefficients of the rook polynomial represent the number of ways "k" rooks, that do not attack each other, can be arranged on an "m" × "n" chessboard. In other words, the rooks are arranged in such a way, that there is no pair of rooks on a rank (row) or a file (column). In this sense, an arrangement is the positioning of rooks on a static, immovable board; the arrangement will change if the board is rotated. The rook polynomial, "R_m,n"("x"), is the generating function for such arrangements:

: $R\_\{m,n\}(x)=\; sum\_\{k=0\}^\{min(m,n)\}r\_k\; x^k$

The first few rook polynomials on square "n" × "n" boards are ($R\_n\; equiv\; R\_\{n,n\}$):

:

In words, this means that on a 1 × 1 board, 1 rook can be arranged in 1 way, and zero rooks can also be arranged in 1 way (empty board); on a 2 × 2 board, 2 rooks can be arranged in 2 ways (on the diagonals), 1 rook can be arranged in 4 ways, and zero rooks can be arranged in 1 way; and so forth for larger boards.

For non-square, "m" × "n" rectangular boards, with "m" ≠ "n", the smaller value is taken as an upper limit for "k", as shown in the formula for "R_m,n"("x" ). For boards of irregular shape, such as the Young tableau (also known as Ferrers diagram, Ferrers board, Ferrers graph), "R_n"("x") is usually a composite, derived by an addition or multiplication of "R_m,n"("x") for square or rectangular boards.

The rook polynomial is closely related to the generalized Laguerre polynomial $L\_n^\{(alpha)\}(x)$ by the relationship:

: $R\_\{m,n\}(x)=\; n!\; x^n\; L\_n^\{(m-n)\}(-x^\{-1\}).$

The term "rook polynomial" was coined by John Riordan. [ [http://books.google.com/books?id=zWgIPlds29UC "Introduction to Combinatorial Analysis"] Princeton University Press (originally published by John Wiley and Sons, Inc, New York; Chapman and Hall, London, 1958, reissue 1980) ISBN 978-0691023656 (reprinted again in 2002, by Courier Dover Publications).]

Rooks problem

Chess diagram|=
tright|
=

8 | | | | | | | |rd|= 7 | | | | | | |rd|xo|= 6 | | | | | |rd|xo|xo|= 5 | | | | |rd|xo|xo|xo|= 4 | | | |rd|xo|xo|xo|xo|= 3 | | |rd|xo|xo|xo|xo|xo|= 2 | |rd|xo|xo|xo|xo|xo|xo|= 1 |rd|xo|xo|xo|xo|xo|xo|xo|= a b c d e f g h

Fig. 1. The maximal number of non-attacking rooks on a 8 × 8 chessboard is 8. Rook + dots mark the number of squares on a rank, available to each rook, after placing the rooks on the lower ranks.

The precursor to the rook polynomial is the classic "Eight rooks problem" by H. E. Dudeney [Dudeney, Henry E. Amusements In Mathematics. 1917. Nelson. (republished by Plain Label Books: ISBN 1603031529, also as a collection of newspaper clippings, Courier Dover, 1958; Kessinger Publishing, 2006). The book can be freely downloaded from Project Gutenberg site [http://www.gutenberg.org/etext/16713] ] in which he shows that the maximum number of non-attacking rooks on a chessboard is eight by placing them on one of the main diagonals (Fig. 1). The question asked is: "In how many ways can eight rooks be placed on an 8 × 8 chessboard so that neither of them attacks the other?" The answer is: "Obviously there must be a rook in every row and every column. Starting with the bottom row, it is clear that the first rook can be put on any one of eight different squares (Fig. 1). Wherever it is placed, there is the option of seven squares for the second rook in the second row. Then there are six squares from which to select the third row, five in the fourth, and so on. Therefore the number of different ways must be 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320" (that is, 8!, where "!" is factorial). [Dudeney, Problem 295]

The same result can be obtained in a slightly different way. Let us endow each rook with a positional number, corresponding to the number of its rank, and assign it a name that corresponds to the name of its file. Thus, rook a1 has position 1 and name "a", rook b2 has position 2 and name "b", etc. Then let us order the rooks into an ordered list (sequence) by their positions. The diagram on Fig. 1 will then transform in the sequence (a,b,c,d,e,f,g,h). Placing any rook on another file would involve moving the rook that hitherto occupied the second file to the file, vacated by the first rook. For instance, if rook a1 is moved to "b" file, rook b2 must be moved to "a" file, and now they will become rook b1 and rook a2. The new sequence will become (b,a,c,d,e,f,g,h). In combinatorics, this operation is termed "permutation", and the sequences, obtained as a result of the permutation, are permutations of the given sequence. The total number of permutations, containing 8 elements from a sequence of 8 elements is:

:$P\_8^8\; =\; frac\{8!\}\{(8-8)!\}\; =\; frac\{8!\}\{0!\}\; =\; 8!\; =\; 40,320.$

To assess the effect of the imposed limitation "rooks must not attack each other", let us consider the problem without such limitation. In how many ways can eight rooks be placed on an 8 × 8 chessboard? This will be the total number of combinations of 8 rooks on 64 squares:

:$C\_8^\{64\}\; =\; \{64\; choose\; 8\}\; =\; frac\{64!\}\{8!(64-8)!\}\; =\; 4,426,165,368.$

Thus, the limitation "rooks must not attack each other" reduces the total number of allowable positions from combinations to permutations which is a factor of about 109,776.

A number of problems from different spheres of human activity can be reduced to the rook problem by giving them a "rook formulation". As an example: A company must employ "n" workers on "n" different jobs and each job must be carried out only by one worker. In how many ways can this appointment be done?

Let us put the workers on the ranks of the "n" x "n" chessboard, and the jobs − on the files. If worker "i" is appointed to job "j", a rook is placed on the square where rank "i" crosses file "j". Since each job is carried out only by one worker and each worker is appointed to only one job, all files and ranks will contain only one rook as a result of the arrangement of "n" rooks on the board, that is, the rooks do not attack each other.

Rook polynomial as a generalization of the rooks problem

The classical rooks problem immediately gives the value of "r"₈, the coefficient in front of the highest order term of the rook polynomial. Indeed, its result is that 8 non-attacking rooks can be arranged on an 8 × 8 chessboard in "r"₈ = 8! = 40320 ways.

Let us generalize this problem by considering an "m" × "n" board, that is, a board with "m" ranks (rows) and "n" files (columns). The problem becomes: In how many ways can one arrange "k" rooks on an "m" × "n" board in such a way that they do not attack each other?

It is clear that for the problem to be solvable, "k" must be less or equal to the smaller of the numbers "m" and "n"; otherwise one cannot avoid placing a pair of rooks on a rank or on a file. Let this condition be fulfilled. Then the arrangement of rooks can be carried out in two steps. First, choose the rank on which to place the rook. Since the number of ranks is "m", of which "k" must be chosen, this choice can be done in $extstyle\{C\_k^m\}$ ways. Similarly, the file on which to place the rook, can be chosen in $extstyle\{C\_k^n\}$ ways. Because the choice of files does not depend on the choice of rank, according to the products rule there are $extstyle\{C\_k^mC\_k^n\}$ ways to chose the square on which to place the rook.

However, the task is not yet finished because "k" ranks and "k" files intersect in "k"² squares. Moving those squares when needed, one obtains a new board of "k" ranks and "k" files. It was already shown that on such board "k" rooks can be arranged in "k"! ways (so that they do not attack each other). Therefore, the total number of possible non-attacking rooks arrangements is: [Vilenkin, Naum Ya. Combinatorics (Kombinatorika). 1969. Nauka Publishers, Moscow (In Russian).]

:$r\_k\; =\; C\_k^m\; C\_k^n\; k!\; =\; frac\{n!\; m!\}\{k!\; (n-k)!\; (m-k)!\}.$

For instance, 3 rooks can be placed on a conventional chessboard (8 × 8) in $extstyle\{frac\{8!\; 8!\}\{3!5!5!$ = 18,816 ways. For "k" = "m" = "n", the above formula gives "r_k" = "n"! that corresponds to the result obtained for the classical rooks problem.

The rook polynomial with explicit coefficients is now:

:$R\_\{m,n\}(x)\; =\; sum\_\{k=0\}^\{min(m,n)\}C\_k^m\; C\_k^n\; k!\; x^k\; =\; sum\_\{k=0\}^\{min(m,n)\}frac\{n!\; m!\}\{k!\; (n-k)!\; (m-k)!\}\; x^k.$

If the limitation "rooks must not attack each other" is removed, one must choose any "k" squares from "m" × "n" squares. This can be done in:

:$C\_k^\{m\; n\}\; =\; frac\{(mn)!\}\{k!\; (mn-k)!\}$ ways.

If the "k" rooks differ in some way from each other, e.g., they are labelled or numbered, all the results obtained so far must be multiplied by "k"!, the number of permutations of "k" rooks.

ymmetric arrangements

As a further complication to the rooks problem, let us require that rooks not only be non-attacking but also symmetrically arranged on the board. Depending on the type of symmetry, this is equivalent to rotating or reflecting the board. For such problems, Dudeney [Dudeney, Answer to Problem 295] observes: "How many ways there are if mere reversals and reflections are not counted as different has not yet been determined; it is a difficult problem." Symmetric arrangements lead to many problems, depending on the symmetry condition. [Vilenkin, Naum Ya. Popular Combinatorics (Populyarnaya kombinatorika). 1975. Nauka Publishers, Moscow (In Russian).] [Gik, Evgeny Ya. Mathematics on the Chessboard (Matematika na shakhmatnoy doske). 1976. Nauka Publishers, Moscow (In Russian).] [Gik, Evgeny Ya.Chess and Mathematics (Shakhmaty i matematika). 1983. Nauka Publishers, Moscow (In Russian). ISBN 3-87144-987-3 ( [http://gso.gbv.de GVK-Gemeinsamer Verbundkatalog] )] [Kokhas', Konstantin P. Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny). MCNMO, Moscow, 2003 (in Russian). ISBN 5-94057-114-X ( [http://gso.gbv.de GVK-Gemeinsamer Verbundkatalog] )] Chess diagram|=
tright|
=

8 | |rd| | | | | | |= 7 | | | | | | | |rd|= 6 | | | | |rd| | | |= 5 | | |rd|xo|xo| | | |= 4 | | | |xo|xo|rd| | |= 3 | | | |rd| | | | |= 2 |rd| | | | | | | |= 1 | | | | | | |rd| |= a b c d e f g h

Fig. 2. A symmetric arrangement of non-attacking rooks about the centre of a 8 × 8 chessboard. Dots mark the 4 central squares that surround the centre of symmetry.The simplest of those arrangements is when rooks are symmetric about the centre of the board. Let us designate with "G_n" the number of arrangements in which "n" rooks are placed on a board with "n" ranks and "n" files. Now let us make the board to contain 2"n" ranks and 2"n" files. A rook on the first file can be placed on any of the 2"n" squares of that file. According to the symmetry condition, placement of this rook defines the placement of the rook that stands on the last file − it must be arranged symmetrically to the first rook about the board centre. Let us remove the first and the last files and the ranks that are occupied by rooks (since the number of ranks is even, the removed rooks cannot stand on the same rank). This will give a board of 2"n" − 2 files and 2"n" − 2 ranks. It is clear that to each symmetric arrangement of rooks on the new board corresponds a symmetric arrangement of rooks on the original board. Therefore, "G"_2"n" = 2"nG"_{2"n" − 2} (the factor 2"n" in this expression comes from the possibility for the first rook to occupy any of the 2"n" squares on the first file). By iterating the above formula one reaches to the case of a 2 x 2 board, on which there are 2 symmetric arrangements (on the diagonals). As a result of this iteration, the final expression is "G"_2"n" = 2^"n""n"! For the usual chessboard (8 x 8), "G"₈ = 2⁴ x 4! = 16 x 24 = 384 centrally symmetric arrangements of 8 rooks. One such arrangement is shown in Fig. 2.

For odd-number boards (containing 2"n" + 1 ranks and 2"n" + 1 files) there is always a square that does not have its symmetric double − this is the central square of the board. There must always be a rook placed on this square. Removing the central file and rank, one obtains a symmetric arrangement of 2"n" rooks on an 2"n" x 2"n" board. Therefore, for such board, once again "G"_{2"n" + 1} = "G"_2"n" = 2^"n""n"!

A little more complicated problem is to find the number of non-attacking arrangements that do not change upon 90° rotation of the board. Let the board has 4"n" files and 4"n" ranks, and the number of rooks is also 4"n". In this case, the rook that is on the first file can occupy any square on this file, except the corner squares (a rook cannot be on a corner square because after a 90° rotation there would 2 rooks that attack each other). There are another 3 rooks that correspond to that rook and they stand, respectively, on the last rank, the last file, and the first rank (they are obtained from the first rook by 90°, 180°, and 270° rotations). Removing the files and ranks of those rooks, one obtains the rook arrangements for a (4"n" − 4) x (4"n" − 4) board with the required symmetry. Thus, the following recurrent relationship is obtained: "R"_4"n" = (4"n" − 2)"R"_{4"n" − 4}, where "R_n" is the number of arrangements for a "n" x "n" board. Iterating, it follows that "R"_4"n" = 2"n"(2"n" − 1)(2"n" − 3)...1. The number of arrangements for a (4"n" + 1) x (4"n" + 1) board is the same as that for a 4"n" x 4"n" board; this is because on a (4"n" + 1) x (4"n" + 1) board, one rook must necessarily stand in the centre and thus the central rank and file can be removed. Therefore "R"_{4"n" + 1} = "R"_4"n". For the traditional chessboard ("n" = 2), "R"₈ = 4 x 3 x 1 = 12 possible arrangements with rotational symmetry.

For (4"n" + 2) x (4"n" + 2) and (4"n" + 3) x (4"n" + 3) boards, the number of solutions is zero. Two cases are possible for each rook: either it stands in the centre or it doesn't stand in the centre. In the second case, this rook is included in the rook quartet that exchanges squares on turning the board at 90°. Therefore, the total number of rooks must be either 4"n" (when there is no central square on the board) or 4"n" + 1. This proves that "R"_{4"n" + 2} = "R"_{4"n" + 3} = 0.

The number of arrangements of "n" non-attacking rooks symmetric to one of the diagonals (for determinacy, the diagonal corresponding to a1-h8 on the chessboard) on a "n" x "n" board is "Q_n" = "Q"_{"n" − 1} + ("n" − 1)"Q_{n" − 2}. This recurrence is derived in the following way. Note that the rook on the first file either stands on the bottom corner square or it stands on another square. In the first case, removal of the first file and the first rank leads to the symmetric arrangement "n" − 1 rooks on a ("n" − 1) x ("n" − 1) board. The number of such arrangements is "Q_{n" − 1}. In the second case, for the original rook there is another rook, symmetric to the first one about the chosen diagonal. Removing the files and ranks of those rooks leads to a symmetric arrangement "n" − 2 rooks on a ("n" − 2) x ("n" − 2) board. Since the number of such arrangements is "Q_{n" − 2} and the rook can be put on the "n" − 1 square of the first file, there are ("n" − 1)"Q_{n" − 2} ways for doing this, which immediately gives the above recurrence. The number of diagonal-symmetric arrangements is then given by the expression:

:$Q\_n\; =\; 1\; +\; C\_2^n\; +\; frac\{1\}\{1\; imes\; 2\}C\_2^nC\_2^\{n-2\}\; +\; frac\{1\}\{1\; imes\; 2\; imes\; 3\}C\_2^nC\_2^\{n-2\}C\_2^\{n-4\}\; +\; ldots$

This expression is derived by partitioning all rook arrangements in classes; in class "s" are those arrangements in which "s" pairs of rooks do not stand on the diagonal. In exactly the same way, it can be shown that the number of "n"-rook arrangements on a "n" x "n" board, such that they do not attack each other and are symmetric to both diagonals is given by the recurrence equations "B"_2"n" = 2"B"_{2"n" − 2} + (2"n" − 2)"B"_{2"n" − 4} and "B"_{2"n" + 1} = "B"_2"n".

References