In this sense, an arrangement is the positioning of rooks on a static, immovable board; the arrangement will not be different if the board is rotated or reflected while keeping the squares stationary.
The term "rook polynomial" was coined by John Riordan.
Famous examples include the number of ways to place n non-attacking rooks on: Interest in rook placements arises in pure and applied combinatorics, group theory, number theory, and statistical physics.
is the number of ways to place k non-attacking rooks on the board B.
The rook polynomial Rm,n(x) corresponds to the complete bipartite graph Km,n .
The rook polynomial of a general board B ⊆ Bm,n corresponds to the bipartite graph with left vertices v1, v2, ..., vm and right vertices w1, w2, ..., wn and an edge viwj whenever the square (i, j) is allowed, i.e., belongs to B.
We deduce an important fact about the coefficients rk, which we recall given the number of non-attacking placements of k rooks in B: these numbers are unimodal, i.e., they increase to a maximum and then decrease.
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?"
Starting with the bottom row, it is clear that the first rook can be put on any one of eight different squares (Fig.
This will be the total number of combinations of 8 rooks on 64 squares: 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.
Let us put the workers on the ranks of the n × 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.
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.
However, the task is not yet finished because k ranks and k files intersect in k2 squares.
that corresponds to the result obtained for the classical rooks problem.
Depending on the type of symmetry, this is equivalent to rotating or reflecting the board.
Symmetric arrangements lead to many problems, depending on the symmetry condition.
[7][8][9][10] The simplest of those arrangements is when rooks are symmetric about the centre of the board.
Let us designate with Gn the number of arrangements in which n rooks are placed on a board with n ranks and n files.
Therefore, G2n = 2nG2n − 2 (the factor 2n in this expression comes from the possibility for the first rook to occupy any of the 2n squares on the first file).
By iterating the above formula one reaches to the case of a 2 × 2 board, on which there are 2 symmetric arrangements (on the diagonals).
Removing the central file and rank, one obtains a symmetric arrangement of 2n rooks on a 2n × 2n board.
A little more complicated problem is to find the number of non-attacking arrangements that do not change upon 90° rotation of the board.
Thus, the following recurrence relation is obtained: R4n = (4n − 2)R4n − 4, where Rn is the number of arrangements for a n × n board.
Therefore, the total number of rooks must be either 4n (when there is no central square on the board) or 4n + 1.
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) × (n − 1) board.
In exactly the same way, it can be shown that the number of n-rook arrangements on a n × n board, such that they do not attack each other and are symmetric to both diagonals is given by the recurrence equations B2n = 2B2n − 2 + (2n − 2)B2n − 4 and B2n + 1 = B2n.
A different type of generalization is that in which rook arrangements that are obtained from each other by symmetries of the board are counted as one.
For instance, if rotating the board by 90 degrees is allowed as a symmetry, then any arrangement obtained by a rotation of 90, 180, or 270 degrees is considered to be "the same" as the original pattern, even though these arrangements are counted separately in the original problem where the board is fixed.
The problem reduces to that of counting symmetric arrangements via Burnside's lemma.