| MANSW | The Mathematical Association of New South Wales, Inc. Promoting Quality Mathematics Education for all. |
MATHSEARCH99 Project99
Prepared by Geoff Ball and Humphrey Gastineau-Hills, University of Sydney.
Dongboard Counting - page 4
Non-interfering donghoards.
Suppose the cells of a dongboard C are separated into two or more
subsets.
Each of these subsets forms a dongboard called a sub-board of
C.
We say that such sub-dongboards are non-interfering if no row
or column of C contains cells from more than one of these
sub-dongboards.
For example: Figure 3 can be split into two non-interfering
sub-dongboards, a 2 x 2 square C1 and a 1 x 2 rectangle
C2.
Note that the placement of an R in C1 is
independent of the placement of an R in C2.
This yields the following technique.
Technique 1: If a dongboard C can be broken up into g non-interfering
dongboards
C1, C2, • • •, Cg
then the rook polynomial of C is the product of the rook polynomials
of these non-interfering dongboards C1, C2, • • •, Cg.
|
|
|
|
|
|
Figure 6 |
Figure 7. |
Figure 8(a). |
Figure 8(b). |
Exercise 7.
Show clearly that the dongboard C in Figure 6 can be split
into two non-interfering dongboards. Hence use technique 1 to
calculate the rook polynomial of C.
Single cell expansion.
There are, of course, dongboards that do not split into
non-interfering parts.
A more general technique uses the notion of inclusion and exclusion
and is called the single cell expansion formula for the
corresponding rook polynomial:
1. Select any cell, say x, in dongboard C.
2. We create two new dongboards from C, called for reasons that
become apparent:
The inclusive dongboard, Ci obtained from C by
deleting the entire row and column containing x (including cell x
itself);
The exclusive dongboard, Ce obtained from C by
deleting just the selected cell x.
Exercise 8.
(a) Show that, with the notation as above, rp(C) =
rp-1(Ci) + rp(Ce).
(b) Deduce that the rook polynomial R(t, C) is given by R(t, c) =
tR(t, Ci) + R(t, Ce).
Technique 2: The process of creating a rook polynomial using
inclusion and exclusion as in Exercise 8 is called single cell
expansion.
Exercise 9.
(a) Taking the cell marked x as the selected cell in Figure 7,
use the single cell expansion formula (even if you have not been able
to prove this formula) in conjunction with non-interfering dongboards
to show that the rook polynomial for the dongboard C in Figure 7
is:
R(t, C) = 1 + 6t + 8t2 + 2t3
(b) Find the rook polynomial of each of the dongboards (a) and (b) in
Figure 8.
