Problems in Combinatorics

PROBLEMS IN COMBINATORICS SEBASTIAN VATTAMATTAM 1. Arrangements with Forbidden Positions Problem 1.1. Example 8:11 in the Book [1]. Four people R1;R2;R3;R4; and ve tables T1; T2; T3; T4; T5- to be seated only one on a table, under the conditions, (1) R1 won't sit on T1; T2 (2) R2 won't sit on T2 (3) R3 won't sit on T3; T4 (4) R4 won't sit on T4; T5 Find the number of arrangements. Figure 1. The Chessboard C Reformulating the problem: Given, Date: 29 - 06 - 10. Key words and phrases. Forbidden Positions, Rook Polynomial. 12 SEBASTIAN VATTAMATTAM (1) Four rooks R1;R2;R3;R4; (2) Five columns C1;C2;C3;C4;C5 of C (3) Four Conditions (a) C1;C2 are forbidden for R1 (b) C2 is forbidden for R2 (c) C3;C4 are forbidden for R3 (d) C;C5 are forbidden for R4 We have to nd the number of arrangements of the our rooks in dierent columns, satisfying the above 4 conditions. Since the shaded squares are less in num- ber, it is easier to work with the shaded chessboard. To Apply the Principle of Inclusion and Ex- clusion S - the set of possible arrangements of the four rooks, one in a column jSj = N = S0 = 5! The condition ci; i = 1; 2; 3; 4 - Ri is in a forbid- den(shaded) position. N(ci); i = 1; 2; 3; 4 - the number of arrangements in S, satisfying ci: (a) N(c1) = 4! + 4! (b) N(c2) = 4! (c) N(c3) = 4! + 4! (d) N(c4) = 4! + 4! (e) Therefore, S1 = 7:4! (a) N(c1c2) = 3! (b) N(c1c3) = 4:3! (c) N(c1c4) = 4:3! (d) N(c2c3) = 2:3! (e) N(c2c4) = 2:3! (f) N(c3c4) = 3:3! (g) Therefore, S2 = 16:3!COMBINATORICS 3 Now, nding Si; i 3 is not so easy. We take another route. Decomposing the chessboard of shaded cells, we nd the Rook polynomial r(C; x) as follows: Let C1 be the top-left subboard and C2 the bottom- right subboard. Then, r(C1; x) = 1 + 3x + x2 From Figure 2, Figure 2. The Subboard C2 r(C2; x) = 1 + 4x + 3x2 Therefore, r(C; x) = (1+3x+x2)(1+4x+3x2) = 1+7x+16x2+13x3+3x4 r0 = 1; r1 = 7; r2 = 16; r3 = 13; r4 = 3 We have seen, S1 = 7:4! = r1(5 􀀀 1)!; S2 = 16:3! == r2(5 􀀀 2)!4 SEBASTIAN VATTAMATTAM In general, Si = ri(5 􀀀 i)!; 1 i 4 Therefore, N(c1c2c3c4) = S0 􀀀 S1 + S2 􀀀 S3 + S4 = 5! 􀀀 7:4! + 16:3! 􀀀 13:2! + 3:1! = 25 The four Conditions c1 - the set of possible arrangements of the four rooks, one in a column jSj = N = S0 = 5! Problem 1.2. Example 8:12 in Book [1] Two dice - red die R and green die G - both thrown together 6 times - what is the probability that on each die the six 'die-numbers' occur, under the condition that the following ordered pairs do not occur. (1; 2); (2; 1); (2; 5); (3; 4); (4; 1); (4; 5); (6; 6); where for (a; b) a is on R and b is on G. If a is a number on R and b is on G, each of the six throws gives a pair (a; b): The chessboard (a) in Figure 3 represents the 36 such pairs. The shaded cells represent the forbidden cases. First let us nd the Rook polynomial for the Chessboard (a): Rearranging the rows and columns, we get the chess- board (b) The 2 2 subboard has the Rook polynomial 1 + 4x + 2x2 and each 1subboard has the Rook polynomial 1 + x Therefore, r(C; x) = (1+4x+2x2)(1+x)3 = 1+7x+17x2+19x3+10x4+2x5COMBINATORICS 5 Now, consider only the die R. Six throws give a 6-tuple of the form (2; 4; 1; 3; 6; 5). Let S be the set of such possible results. Then jSj = N = 6! Suppose one result is = (2; 4; 1; 3; 6; 5) and the corre- sponding result for G is (2; 1; 4; 3; 6; 5). But, this gives the pair (4; 1) which is in the list of forbidden pairs. So, and such other elements have to be excluded from S. Here, we consider the chessboard of shaded squares. The conditions for that can be stated as follows: for 1 i 6; ci is the condition that i on R is paired with one of the forbidden numbers on G Then, N(c1) = 1 N(c2) = 2 N(c3) = 1 N(c4) = 2 N(c5) = 0 N(c6) = 1 For any clarication please contact vattamattam@gmail.com References [1] Ralph P. Grimaldi,Discrete and Combinaorial Mathmatics,Fourth Edition, Pearson Eucation Asia, 1999 Mary Bhavan, Ettumanoor E-mail address: vattamattam@gmail.com6 SEBASTIAN VATTAMATTAM Figure 3. The Subboard C2