\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Corrections for Problem 32 in Chapter 6 of Brualdi, {\it version 2}}
\centerline{March 14, 2005}
\bigskip
\noindent
Unfortunately, there were several things wrong with problem
32 in Chapter 6 of the text (on Problem Set 5 for the course), {\it 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.
\bigskip
\noindent
A)  {\it This is different from the original ``corrected version''(!)}
Show that if $B_m$ is the
board with $m$ {\it unshaded} squares in locations
$$(1,1),(1,2),(2,2),(2,3), \ldots, $$
in a diagonal ``staircase pattern'' containing exactly $m$ squares, 
then the rook polynomial of $B_m$ is given by:
$$R(B_m,t) = 1 + {m\choose 1} t + {m-1\choose 2}t^2 + 
{m-2\choose 3} t^3 + \cdots + {m-k+1\choose k} t^k + \cdots $$
(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 \times 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.)
\bigskip
\noindent
B)  Use part A and our theorems on rook polynomials
to show that the rook polynomial of the complement $\overline{B}$ of the 
$n\times n$ board $B$ given in the book problem is
$$R(\overline{B},t) = \sum_{k=0}^n {2n\over 2n - k} {2n - k \choose k} t^k$$
\bigskip
\noindent
C) Use part B to find the number of ways of placing $n$ non-attacking
rooks on the {\it unshaded} squares in the book's $n\times n$ board $B$.
\bigskip
\noindent
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!)
\bye

