ROOK POLYNOMIALS AND THE PRINCIPLE OF INCLUSION AND EXCLUSION SEBASTIAN VATTAMATTAM 1. Basic Definitions 1 • C a chessboard • A rook can move only along a row or column • k 2 Z+ is the number of rooks • Two rooks can take each other means they are in the same row or column. A set of rooks is nontaking if no two of them can take each other. • rk(C) is the number of ways in which k rooks can be placed in the squares in C so that no two of them take each other • r1(C) is the number of squares on C Example 1.1. 3 2 1 4 X X X 5 6 In 1.1, (1) r1 = 6 (2) If k = 2 the non-taking pairs of positions are (1, 4), (1, 5), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5), (4, 6), r2 = 8 (3) If k = 3 the non-taking triads of positions are (1, 4, 5), (2, 4, 6) Date: 03 -03 -10. Key words and phrases. Rook, Polynomial. 1Ralph P. Grimaldi, Discrete and Combinatorial Mathematics 12 SEBASTIAN VATTAMATTAM r3 = 2 (4) rk = 0, 8k 4 (5) r0 = 1 Now, consider the polynomial r(C, x) = r0 + r1x + r2x2 + r3x3 + r4x4 + · · · = 1 + 6x + 8x2 + 2x3 Definition 1.1. If C is a chessboard, with n squares(cells), then the polynomial r(C, x) = 1 +Xn1 rk(C)xk is called a Rook polynomial. Subboards Example 1.2. 1 2 X X X 3 4 X X X X X X 5 6 X X X 7 8 X X 9 10 11 In 1.2, the chessboard C has 11 unshaded cells, which are partitioned into two: (1) The top-left 4 cells, C1, and (2) the bottom-right 7 cells, C2 C1,C2 are called subboards. Two subboards C1,C2 are disjoint if no cell in C1 is in the same row or column of a cell in C2. Consider C1 (1) r0 = 1 (2) r1 = 4 (3) If k = 2 the non-taking pairs of positions are (1, 4), (2, 3) r2 = 2DISCRETE MATH 3 (4) rk = 0, 8k 3 r(C1, x) = 1 + 4x + 2x2 Similarly we can see, r(C2, x) = 1 + 7x + 10x2 + 2x3 Theorem 1.2. If a chessboard C consists of pairwise disjoint subboards C1,C2,C3, · · ·Cn, then (1.1) r(C, x) = r(C1, x)×r(C2, x)×r(C3, x)×· · · r(Cn, x) Applying theorem 1.1 to Example 1.2, we have r(C, x) = (1+4x+2x2)×(1+7x+10x2+2x3) = 1+11x+40x2+56x3+28x4+4x5 Example 1.3. Figure 1. Chessboard C and its subboards Cs and Ce Consider the Chessboard C in Figure 1(a). Suppose there are k 1 rooks. First let us fill the cell []. There are two cases:4 SEBASTIAN VATTAMATTAM Figure 2. The Chessboard split into smaller and smaller subboards (1) A rook is placed in []. In this case the cells below [] cannot be used. Deleting them we get the chessboard (b), which we call Cs. Now there are only k −1 rooks for Cs. and hence rk−1(Cs) is their number of possible positioning.DISCRETE MATH 5 (2) No rook is placed in []. Removing that cell we get the chessboard (c), which we call Ce. Now there are k rooks for Ce and hence rk(Ce) is their number of possible positioning. Thus we get, (1.2) rk(C) = rk−1(Cs) + rk(Ce) Multiplying with xk, (1.3) rk(C)xk = rk−1(Cs)xk + rk(Ce)xk Since n = 8 is the number of cells in C, summing yields, Xn k=1 rk(C)xk = Xn k=1 rk−1(Cs)xk + Xn k=1 rk(Ce)xk = x Xn k=1 rk−1(Cs)xk−1 + Xn k=1 rk(Ce)xk Adding 1 on both sides, 1 + Xn k=1 rk(C)xk = x Xn k=1 rk−1(Cs)xk−1 + Xn k=1 rk(Ce)xk + 1 r(C, x) = x × r(Cs, x) + r(Ce, x) Now we proceed as indicated by the figure 2 2. Principle of Inclusion and Exclusion Notations[1], Chapter 8 • S -a set and |S| = N its cardinality. • ci, i = 1, 2, · · · t -conditions on the elements of S. • N(ci) -number of elements in S that satisfy ci. • N(cicj), i 6= j -number of elements in S that satisfy both ci, cj • N(¯ci) = N −N(ci) -number of elements in S that do not satisfy ci. • N(¯ci¯cj) -number of elements in S that do not satisfy either ci or cj6 SEBASTIAN VATTAMATTAM • ¯N= N(¯c1¯c2...¯ct) -number of elements in S that do not satisfy any of the conditions. Theorem 2.1. Principle of Inclusion and Exclusion Let S0 = N S1 = N(c1) + N(c2) + ...N (ct) S2 = X 1ijtN(cicj) S3 = ............ Then, (2.1) ¯N= S0 − S1 + S2 − ... + (−1)tN(c1c2...ct) Example 2.1. Find the number of positive integers less than or equal to 100, which are not divisible by 2, 3, or 5. Solution S = {1, 2, ...100},N = 100 For n 2 S, (1) c1 -n is divisible by 2 (2) c2 -n is divisible by 3 (3) c3 -n is divisible by 5 We have to find N(¯c1¯c2¯c3) Let xxy denote the greatest integer not greater than x. Then, (1) N(c1) = x100 2 y = 50 (2) N(c2) = x100 3 y = 33 (3) N(c3) = x100 5 y = 20 (4) N(c1c2) = x100 6 y = 16 (5) N(c1c3) = x100 10 y = 10 (6) N(c2c3) = x100 15 y = 6 (7) N(c1c2c3) = x100 30 y = 3DISCRETE MATH 7 S0 = 100 S1 = N(c1) + N(c2) + N(c3) = 103 S2 = N(c1c2) + N(c1c3) + N(c2c3) = 32 S3 = N(c1c2c3) = 3 Therefore N(¯c1¯c2¯c3) = S0 − S1 + S2 − S3 = 26 References [1] Ralph P. Grimaldi,Discrete and Combinaorial Mathmatics,Fourth Edition, Pearson Eucation Asia, 1999 Mary Bhavan, Ettumanoor E-mail address: vattamattam@gmail.com