Mathematics 357 – Combinatorics Corrections for Problem 32 in Chapter 6 of Brualdi, version 2 March 14, 2005

Unfortunately, there were several things wrong with problem 32 in Chapter 6 of the text (on Problem Set 5 for the course), and also with the first corrected version (!) (There must be something about this problem!) Here is a corrected version of the problem, incorporating some hints that should help you get started toward a solution.

A) This is different from the original “corrected version”(!) Show that if B_{m} is the board with m unshaded squares in locations

(1, 1), (1, 2), (2, 2), (2, 3), …,

in a diagonal “staircase pattern” containing exactly m squares, then the rook polynomial of B_{m} is given by:

R(B_{m}, t) = 1 + \binom{m}{1}t + \binom{m − 1}{2}t^{2} + \binom{m − 2}{3}t^{3} + ⋯ + \binom{m − k + 1}{k}t^{k} + ⋯

(Note: B_{2n−1} is the “upper part” of the shaded squares in the board in the book problem – there are m = n + n − 1 = 2n − 1 X’s. The cases B_{m} with m = 2n − 1 odd fit on n × n boards; the cases with m = 2n even don’t quite fit on square boards if the top of the staircase occurs in row 1, column 1.)

B) Use part A and our theorems on rook polynomials to show that the rook polynomial of the complement \overline{B} of the n × n board B given in the book problem is

R(\overline{B}, t) = ∑_{k=0}^{n} \frac{2n}{2n − k} \binom{2n − k}{k}t^{k}

C) Use part B to find the number of ways of placing n non-attacking rooks on the unshaded squares in the book’s n × n board B.

Comment: This problem is a version of the “hostess problem”: In how many ways can n married couples be seated at a round table so that no husband sits next to his own wife. Do you see the connection? (Think of a round table, but ignore the circular symmetry!)