| 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 2
Example 1.
|
|
|
Figure 2. |
|
Figure 1 is the 4 x 4 bongboard for the permutation = [ 4 1 3 2 ] of S4. Note that in this permutation, the number 4 appears in position 1 and so there is an R in cell (4,1) (column 4, row 1).
Exercise 1: Construct the 6 x 6 bonghoard for the
permutation [ 3 5 1 6 4 2 ].
Exercise 2: Write down the permutation represented by the
bongboard in Figure 2.
Exercise 3: (a) The identity permutation of Sn is
the arrangement of Sn in ascending order. Construct the
bongboard for the identity permutation of S4.
(b) Explain why a bongboard representing a permutation cannot have
two mutually taking rooks. i.e., two rooks on the same row or on the
same column.
Typically, interesting permutations are those in which some
element of Sn, say p, cannot occur in say position q; that
is, that no R will appear in cell (p, q).
Definition 2. Dongboard. When such conditions are imposed, the
corresponding cell (p, q) will be removed from the n x n hoard.
Any n x n board or one resulting from one or more such deletions will
be called a dongboard.
Note: Two rooks on the same row or column do not become non-taking on
the removal of one or more cells between them.
Dongboards will he characterised by the number of cells they contain
and the number of rows into which these are arranged. Thus the
dongboard shown in Figure 3 is referred to as a 3-row
dongboard (with 6 cells) or just a 3-row bongboard.
The Main Thrust of the Project.
Most of the project will be concerned with the number of different
ways of placing j non-taking rooks, 
,
on a k-row bongboard.
Exercise 4. (a) In how many ways can we place 3 rooks on a 3 x 3
hoard?
(b) In how many of these ways are the rooks mutually non-taking?
Notation: If C is a bongboard with n cells we will write
rj(C) for the number of ways of placing j mutually
non-taking rooks on C.
Definition 8: Rook Polynomial. The polynomial function
o<j<k is called the generating function, or rook polynomial, of
the k-row bongboard C. (If you haven't come across this sigma
notation before, please ask your teacher.)
Note: The first term of this polynomial is in fact
r0(C)t0.
