MATHSEARCH99 Project99
Prepared by Geoff Ball and Humphrey Gastineau-Hills, University of Sydney.

Dongboard Counting - page 6

For starters, consider the following problem.

Exercise 12. Determine possible geometric operations which would transform sequentially the dongboard C₁ in Figure 10 through each of the other two dongboards C₂ and C₃ to C₄.

Figure 10



To complete this project you should now continue this investigation to more general cases.

Alternative B. Staircase Dongboards.

Dongboards which cannot be broken into non-interfering sub-boards are said to be connected. Of the connected dongboards, staircase dongboards are of particular interest.
The two diagrams in Figure 11 illustrate k-row staircase dongboards with n = 2k&emdash;1 cells and n = 2k cells respectively.



Figure 11.

This section of the project looks at such connected dongboards.
To get you started, here are a couple of exercises.

Exercise 13. (a) Equivalence creates separate classes of dongboards. For n = 3 for instance, there are just two classes (one containing a staircase). Find the rook polynomials for these two equivalence classes.

(b) Use single cell expansion to express the rook polynomial for the staircase dongboard for n = 3 in terms of the corresponding rook polynomials for the staircase dongboards for n = 2 and n = 1.

Your further investigation should include:

(i) generalising the result in Exercise 13 (b), i.e., finding a recurrence relation;

(ii) listing the rook polynomials for n-cell staircase dongboards for indicating how single cell expansion gives the case n in terms of the cases n-1 and n-2;

(iii) finding any connections with Fibonacci numbers.

We hope you enjoyed this project and that it has helped you extend your mathematical horizons somewhat.

Please include a short note indicating if either of these outcomes were achieved.

1 2 3 4 5 6