1999 Mathsearch: Dongboard Counting

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 3

Example 2: Please check out the details of this example carefully.


Figure 3.	Figure 4.	Figure 5.

The rook polynomial for the 3-row dongboard in Figure 3 is 1 + 6t + 10t² + 4t³.

To see this we can do a cell-listing of the ways in which R's can be placed on the dongboard. Using the notation (1,2),(2,3) for the placement of an R in cell (1,2) (i.e., column 1, row 2) and another R in cell (2,3) (col 2, row 3) the following is the cell-listing of the 10 pairs of cells into which 2 non-taking rooks could be placed (notice the systematic way of listing which exhausts all possibilities beginning in column 1 and progressing from left to right):

(1, 2), (2, 3);	(1, 2), (3, 1);	(1, 2), (4, 1);
(1, 3), (2, 2);	(1, 3), (3, 1);	(1, 3), (4, 1);
(2, 2), (3, 1);	(2, 2), (4, 1);
(2, 3), (3,1)	and (2, 3)(4,1).

Since there are 10 such pairings, the coefficient of t² in the generating function for this dongboard is 10. You should check out the coefficients in the other terms of the polynomial.

Exercise 5:
(a) For

, do a cell-listing for the placement of j non-taking rooks on the dongboard in Figure 4, and hence show that the rook polynomial for this dongboard is

1 +5t+9t² +7t³ +2t⁴

(b) Determine the rook polynomial for the 3-row dongboard in Figure 5.

Exercise 6:

(a) For each value determine the rook polynomial for the square n x n dongboard.

(b) Let . Find an expression for the coefficient of t_j for the n x n square dongboard.

Some Counting Techniques:

You will have found that it is not easy to count the number of ways of placing j non-taking rooks on a k-row dongboard, even when j and k are quite small. Furthermore, you might well wonder how the use of generating functions could possibly help us with the counting. So far we have had to do the counting in order to find the rook polynomial!
Can we reverse the process?
In fact the use of some properties of dongboards can help determine the rook polynomials, hence eliminating the need for tedious counting.