Unknown

8 1. Fundamentals

can enlist the aid of rook polynomials to help us avoid omissions or repeats

in our counting.

Let an m x n (m rows, n columns) chessboard C be given, with some of

its squares forbidden. For each nonnegative integer k, let rk be the number

of ways of placing k rooks so that none is on a forbidden square and no

two are in the same row or column. By convention, ru = 1. Also, rk = 0 if

k > c = min(m, n). The rook polynomial R(C; t) is defined to be

rg + rlt + r2t2 +.. ’ + rCtc.

Since smaller chessboards have shorter and more easily defined rook polyno-

mials, we look for ways of building more complex polynomials from simple

ones.

Suppose S is one of the available squares on the chessboard C. Form

chessboards Cr and C2 as follows:

(1) Ci is the same as C except that the square S is forbidden;

(2) C2 is the (m - 1) x (n - 1) board obtained from C by deleting the

entire row and column containing S.

Let R(C1; t) and R(C2; t) be the corresponding rook polynomials.
Show that R(C; t) = R(C1; t) + tR(C2; t).
Apply this process to obtain the rook polynomial for the problem of the
delivery trucks. Read off from its coefficients the number of ways in which
the dispatcher can send out one, two or three trucks, and give the answer
to the problem.
Here are some further questions to consider:
(a) What is the rook polynomial of an m x n board with no forbidden
squares?
(b) Other sorts of generating functions can be found. Consider the prob-
lem of choosing 6 coins from among 3 coppers, 2 nickels, 2 dimes, 1 quarter
and 1 half-dollar. You are permitted more than one coin of any denomina-
tion; coins of the same value are regarded as indistinguishable. To tackle
the problem systematically, introduce a variable t to act as a counter for
the number of coins, and the symbols c, n, d, q, h for the coins. We can
think of the product nd2q as standing for the choice of four coins consisting
of one nickel, two dimes and one quarter. Using the counter t, we form the
term nd2qt4 with the exponent oft indicating the number of coins chosen.
Let

P(t) = (1 + ct + c2t2 + c3t3)(1 + nt + n2t2)(1 + dt + d2t2)(1 + qt)(l + ht).

Expand P(t) in ascending powers of t and interpret the coefficients. In

particular, what is the relevance of the coefficient of t6 to our problem?

Now set c = n = d = q = h = 1. How do you interpret the coefficients

now? What is the solution to the coin problem?