Question

Combinatorics

29. Suppose B is an n x n board and r,(B) is the coefficient of " in the rook polynomial R(C, B). Use recurrence relations to compute r(B) if (a) B has all squares darkened; (b) B has only the main diagonal lightened.

Answer 1

Let B be a board of darkened squares that decomposes into disjoint subboards
B1 and B2. Then
rk(B) = rk(B1)r0(B2) + rk−1(B1)r1(B2) + ... + r0(B1)rk(B2).
Now we define the rook polynomial R(x, B) of the board B as follows:
R(x, B) = r0(B) + r1(B)x + r2(B)x2 + r3(B)x3 + ... + rn(B)x
n + ...

Let B be a board of darkened squares that decomposes into disjoint subboards
B1 and B2. Then
R(x, B) = R(x, B1)R(x, B2).
Proof:
R(x, B) = r0(B) + r1(B)x + r2(B)x2 + r3(B)x3 + ... =
1 + [r1(B1)r0(B2) + r0(B1)r1(B2)]x + [r2(B1)r0(B2) + r1(B1)r1(B2) + r0(B1)r2(B2)]x
2 + ... =
[r0(B1) + r1(B1)x + r2(B1)x2 + ...] × [r0(B2) + r1(B2)x + r2(B2)x
2 + ...] =
R(x, B1)R(x, B2).
It is interesting to note that the rook polynomial of a board depends only on the darkened
squares, and not on the size of the array containing them. Thus the same groupings of
darkened squares placed in a 5 × 5 array and an 8 × 8 array would yield the same rook
polynomials. Only the final counts attained using the coefficients of the rook polynomials would differ.

R(x, B) = R(x, B1)R(x, B2) = (1 + 3x + x2)(1 + 4x + 3x2) =
1 + [(3 × 1) + (1 × 4)]x + [(1 × 1) + (3 × 4) + (1 × 3)]x
2 + [(1 × 4) + (3 × 3)]x3 + (1 × 3)x4 =1 + 7x + 16x2 + 13x3 + 3x4
.
Armed with our rook polynomial, we can now use the Inclusion-Exclusion Formula to de-
termine how many arrangements of a, b, c, d and e there are that Using the notation of rook polynomials, we can now write
as follows:
Sk = rk(B)(n − k)! (1.5)
And for this problem, where n = 5, we have, the Inclusion-Exclusion Formula, that
N(A1A2A3A4A5) = N − S1 + S2 − S3 + S4 − S5 =
5! − r1(B) × 4! + r2(B) × 3! − r3(B) × 2! + r4(B) × 1! − r5(B) × 0! =
5! − 7 × 4! + 16 × 3! − 13 × 2! + 3 × 1! − 0 × 0! =
120 − 168 + 96 − 26 + 3 − 0 = 25.
Thus we have that there are 25 arrangements of the five letters that will satisfy the restrictions