Welcome to the 1999 MATHSEARCH Project which is organised by The Mathematical Association of N.S.W. to help its committee select Year 11 NSW students to be invited to participate in the prestigious National Mathematics Summer School to be held in Canberra in January 2000.

Project99 is concerned with counting. We will be looking at some devices used to count the number of ways that one can arrange the elements of a set with or without conditions on the placement of its elements.

Background Note 1: For any positive integer n, an arrangement of all the elements of the set S_n = {1, 2, 3, . . ., n}, without repetitions, is called a permutation of the elements of S_n
Notation: Each permutation will be written within square brackets. Thus [2 3 1 4 5] is a permutation of S₅.

Background Note 2: A rook is a chess piece which can move to any square (in an 8 x 8 chessboard) in the same horizontal row or vertical column that it currently occupies. We will use the term cells instead of individual squares.
We will adopt the convention of calling the bottom row: row 1, and the left hand column: column 1. The cell formed by the intersection of column x and row y will be called the cell (x,y).
If two rooks are in the same row or are in the same column, we say that each can take the other.

Background Note 3: The generating function of a sequence r₀, r₁, . . ., r_n is the polynomial f (t) = r₀ + r₁t + + r_ntⁿ.

You might well be asking: What is the connection between these three items?

In 1996, Nguyen-Huu Bong, of the University of Brunei, used the placement of n mutually non-taking rooks on an n x n chessboard to display any permutation of the elements of S-n. It turns out that it is often quite difficult to count the number of permutations when conditions are attached to the placement of the numbers. Generating functions often simplify this process.

Definition 1. Bongboards. A bongboard is the display resulting from the placement of n mutually non-taking rooks on an n x n chessboard to display any permutation of the first n positive integers.

An n x n bongboard is constructed in the following way:

Suppose we have a permutation P of the first n positive integers.
A rook R is placed in cell (p, q) if, in the permutation P, the number p is permuted to position q.

1 2 3 4 5 6