6. Rook polynomials and forbidden positions#

An assignment problem may prohibit some person–position pairings. A rook board keeps those prohibited cells visible while we count only assignments that use allowed cells. The coefficients of a rook polynomial count legal partial assignments; the coefficient for all rows counts legal complete assignments.

After studying these notes, you will be able to do the following.

  • Model allowed assignments by white squares of a board and nonattacking rook placements.

  • Compute rook numbers and the rook polynomial of a small finite board.

  • Use a disjoint-board product and a use-or-omit recurrence to compute a rook polynomial.

  • Use the appropriate rook number to count legal complete assignments.

  • Count injective assignments when there are more positions than objects.

6.1 Special cases of rook numbers#

Definition 1 (Rook numbers)#

Let be a finite collection of allowed squares in a rectangular grid. For an integer , the th rook number is the number of ways to place nonattacking rooks on squares of . The placement with no rooks is allowed, so .

A board with rows and columns has no nonattacking placement of more than rooks. The full boards give a first set of rook numbers that can be counted without examining individual placements.

Example 2 (Four rooks on a full -by- board)#

How many ways are there to place four nonattacking rooks on a full -by- board? Explain why these placements are in bijection with the permutations of .

Solution: A four-rook placement uses four distinct rows and four distinct columns. Since the board has exactly four rows and four columns, it has one rook in every row and one rook in every column. Choose the column for the rook in row , then row , then row , and finally row . There are respectively , , , and choices, so

The word ``equivalently’’ describes the same collection of placements using functions rather than board squares. Let be the set of four-rook placements, and let be the set of bijective functions from to itself. For a placement , define There is exactly one rook in row , so is defined. Distinct rows have rooks in distinct columns, so different inputs have different outputs; because all four columns are used, is bijective. Conversely, for , place a rook at for each . The function assigns one column to each row, and its bijectivity makes those columns distinct, so the rooks are nonattacking. These two instructions undo one another. The left panel of Figure 1, for example, records the permutation .

Example 3 (Derangements on a -by- board)#

Remove the four squares on the main diagonal of a -by- board. How many ways are there to place four nonattacking rooks on the remaining squares?

Solution: Under the bijection in Example 2, the diagonal square records the equation . Thus a placement avoiding every diagonal square corresponds to a permutation with no fixed points: a derangement.

Let be the set of permutations with . If specified positions are fixed, the other positions may be permuted in ways. Inclusion–exclusion gives the desired rook number as Therefore the board without its main diagonal has four-rook placements. The right panel of Figure 1 shows one of them.

Two four-by-four boards. The first is full, with one rook in each row and column, and is labeled with the corresponding permutation. The second has grey diagonal squares and four rooks off the diagonal, representing a derangement.

Figure 1: A full four-by-four board and the board obtained by removing its main diagonal. A full placement represents a permutation; a full placement avoiding the grey diagonal squares represents a derangement.#

Example 4 (Three rooks on a full -by- board)#

How many ways are there to place three nonattacking rooks on a full -by- board?

Solution: A placement has three occupied rows and three occupied columns. First choose its occupied rows, in ways. Next choose its occupied columns, also in ways. These choices leave a -by- intersection grid, as shown in the first two panels of Figure 2.

Each selected row must be paired with a different selected column. Order the three selected rows from top to bottom. The rook in the first selected row has three selected columns available, the next has two, and the final rook has one. Thus the selected intersection grid has nonattacking placements, as the third panel shows. The product rule gives Every placement determines its occupied rows, its occupied columns, and the matching between them. Conversely, those three choices place the rooks. Hence each three-rook placement is counted exactly once.

Three five-by-five board diagrams. The first highlights rows 1, 3, and 5 in blue. The second marks columns 2, 3, and 5 in yellow; the nine cells at selected-row and selected-column intersections are green. The third shows three rooks in different green intersection cells.

Figure 2: Counting three nonattacking rooks on a full five-by-five board. Select three rows, select three columns, and then choose a bijection between the selected rows and columns.#

6.2 General boards for restricted assignments#

Suppose that three students must be assigned, one each, to three presentation slots. Student receives slot , where is a permutation of . The four pairings in the following display are unavailable: For example, says that student cannot receive slot .

Rows of the grid represent students, and columns represent slots. Grey cells are forbidden. The allowed board consists of the white cells: Rooks are placed only on squares of , never on grey cells. A rook at records the legal assignment . Two rooks are nonattacking when they lie in different rows and different columns; then their two assignments can occur together.

Three copies of the same three-by-three grid. In every copy, cells (1,1), (1,3), (2,2), and (3,1) are grey. The first panel has rooks at (1,2) and (3,2), sharing a column. The second has rooks at (1,2) and (2,3), in different rows and columns. The third has one rook at grey cell (1,3), circled in red.

Figure 3: The same forbidden-position board in all three panels. Two rooks in one column attack and give an invalid placement. Two rooks in different rows and columns give a valid placement. A rook on a grey forbidden square is invalid.#

Rook numbers are computed from the allowed board , not from the whole assignment grid. Thus every rook counted by lies on a white square. A placement of nonattacking rooks records legal assignments made at once. For example, the middle panel of Figure 3 records the assignments and .

6.3 One board, counted directly#

Let be the allowed board in Figure 3. We compute every rook number directly. Every square named in the following list belongs to .

The count is easier to check when we keep the board, the legal pairs, and the unique three-rook placement in view at the same time. The figure records those objects before the list below explains why each coefficient has its value.

Four panels tracing the direct count. The first labels the five allowed cells of board B. The second shows six scaled-down copies of the board, each with one valid two-rook placement. The third shows the unique three-rook placement. The fourth displays the values 1, 5, 6, and 1 for zero through three rooks and the polynomial 1 plus 5x plus 6x squared plus x cubed.

Figure 4: A direct count of the rook numbers for . The five allowed cells give ; six unordered pairs use different rows and columns; exactly one three-rook placement is possible; and these values become the coefficients of .#

  • There is one zero-rook placement, so .

  • There are five allowed squares, so .

  • For two rooks, list the unordered pairs of allowed squares that use different rows and columns: Thus . A pair such as is not counted because its two rooks would share row .

  • A three-rook placement must use every row and every column. The only possibility is , so .

No four-rook placement is possible on a board with only three rows. The list of rook numbers is therefore

6.4 Rook polynomials collect all rook numbers#

Counting placements one number at a time repeats the same work whenever we ask about three, four, or five rooks on a larger board. A single polynomial stores all of those counts, with the exponent recording the number of rooks.

Definition 5 (Rook polynomial)#

The rook polynomial of a finite allowed board is The coefficient of is the number of legal nonattacking placements of rooks on .

For the board above, direct enumeration gives The coefficient of records the six two-assignment legal placements, and the coefficient of records the one complete legal assignment.

6.5 Computing rook polynomials without listing every placement#

Direct enumeration is reliable for a small board, but it becomes tedious when there are many possible placements. The product rule and the use-or-omit recurrence reorganize the count.

6.5.1 Boards on disjoint rows and columns#

Suppose and use disjoint sets of rows and disjoint sets of columns. Write for the board formed by taking both sets of squares. A rook placement on this board splits uniquely into a placement on and a placement on ; rooks in one component cannot attack rooks in the other component.

Two four-by-four board diagrams. In the left grid, blue subboard B1 has white allowed squares at (1,1) and (1,2). Green subboard B2 has white allowed squares at (3,3) and (4,4). The subboards have no row or column in common. In the right grid, blue B1 has white allowed squares at (1,1), (1,2), and (1,3). Green B2 has white allowed squares at (3,3), (4,3), and (4,4). Both subboards use column 3, and rooks at (1,3) and (3,3) attack.

Figure 5: The product rule requires both row sets and column sets to be disjoint. At left, a rook placement on can be combined with any rook placement on . At right, the two subboards share column , so placing one rook in each can produce an attacking pair.#

Theorem 6 (Product rule for disjoint rook boards)#

If and occupy disjoint row sets and disjoint column sets, then

The right panel of Figure 5 shows why both conditions are necessary. Disjoint squares alone are not enough: if two subboards share a row or a column, a rook placement in one may attack a rook placement in the other.

Proof#

To form a placement of rooks on , choose an integer between and , place rooks on , and place the remaining rooks on . The decomposition is unique because every square belongs to one component. Therefore The coefficient of in is the same sum. Since the two polynomials have the same coefficient for every , they are equal.

Example 7 (Two separate groups of allowed squares)#

Suppose consists of one allowed square. Suppose consists of two allowed squares in one common row, and all rows and columns of are disjoint from those of . Then because the two squares in attack each other. The combined board has There are three one-rook placements and two ways to choose one rook from each component. There is no three-rook placement, as the zero coefficient also says.

6.5.2 Use or omit an allowed square#

Choose an allowed square of . Every legal rook placement belongs to exactly one of two classes: it either uses or leaves unused. Both classes consist entirely of placements on white allowed squares.

Let denote the allowed board obtained by omitting . Let denote the allowed board remaining after the legal assignment represented by has been fixed: remove the row and column of , since no remaining rook may use either one.

A branching diagram beginning with the three-by-three board whose grey cells are forbidden and whose white cells are allowed. The white square (1,2) is outlined in blue. The upper branch places a rook there, crosses out its row and column, and shows the remaining two-by-two allowed board. The lower branch crosses out square (1,2) only and shows the original allowed board with that square unavailable.

Figure 6: The two classes of legal rook placements at the white allowed square . Using fixes one legal assignment and leaves the smaller allowed board . Omitting leaves the allowed board .#

Theorem 8 (Use-or-omit recurrence)#

For an allowed square of ,

Proof#

Placements that leave unused are precisely the placements on . For a placement that uses , remove the rook at . The remaining rooks form a placement on , and this operation is reversible by restoring the rook at . Restoring that rook increases the number of rooks by one, so the second class contributes .

For the board in Figure 3, choose the white allowed square . If that square is left unused, the remaining allowed board has four squares. Its two-rook placements are , , and , so If a rook is placed at , the remaining legal assignments may use rows and and columns and . The remaining allowed squares are , , and , so The use-or-omit recurrence gives which agrees with the direct calculation.

6.7 What the polynomial has recorded#

The coefficient records the number of legal injective assignments of rows to distinct columns. In particular, counts the legal assignments that use every row. The rook polynomial is a finite first example of a generating function: one algebraic object stores a whole sequence of related counts.

Ordinary generating functions extend this bookkeeping idea from the finite sequence to arbitrary sequences indexed by size.