chapter 3: rook polynomials Flashcards
Rook
a rook challenges another piece if it’s in the same row or column
EXAMPLE: ways of placing on a 3 by 3 board
1,2 and 3
1:9
2:18
choose two ways out of 3, then 3 ways to place a rook in one of the rows, two ways in the second
3:6
3 ways of choosing the first column,2, 1 = 3x2x1 =6
r_B(x)= 1 +9x +18x^2 +6x^3
EXAMPLE: shaded board Rows a b c d, columns 1 2 3 4 can place/unshaded a-3 b-1,2 c-4 d- 1,2
consider number of ways of placing 0 1 2 or 3
0: 1
1: 6
2: 11
(5+2+2+1+1)
3: 8
(4+1)+(2+2)+(1+1)
1+6x +11x^2 +8x^3 +2x^4
definition Rook polynomial
if B is part of an n x n board, the rook polynomial of the board B is
r_B(x)= a_0 + a_1x + a_2 x^2 +…+ a_kx^k +…+ a_nx^n
where a_k= #ways k rooks w/o challenge
a_0= 0 since only one way of placing none
reducing problems to Rooks
for example assignments permutations with shaded boxes
EXAMPLE:#permutations of {1,..,5}
st 1 not sent to 1, 1 not sent to 2, 2 not sent to 2, 2 not sent to 3 ,..
Rook polynomial grid with shaded squares
EXAMPLE:#ways allocating for jobs such that ABCD people abcd jobs
A can’t do b or c
B can’t do a
C can’t do a b or d
D can’t do c or d
shaded squares Rook polynomials
EXAMPLE: hostess problem
5 couples sat alternating man and woman such that not next to partner
1* first shoes women odd or even seats (2)
2sit and label these a b c d e (5! ways= 120)
3 let a be A’s husband I can’t sit in seat 1 or 5 (either side of A) (13 ways)
2x120 x 13 = 3120
EXAMPLE: snap problem
two packs of cards. second part is ordered AC, AH,AD,AS,KC,…,2S. going through the two packs we have a snap if same value(A,1,..2).
how many different orderings of the first Leads to no snap
- number cards 1 to 52 with 1 -4 aces, 5-8 Kings etc. ways of shuffling packed correspond to permutations of {1,..,52}
- if σ is a permutation with σ(9)= 10 then in the corresponding games we have a snap with two Queen’s
- similarly if any σ(9), σ(10) σ(11), σ(12) is in [9,10,11,12} we have a snap
*this to avoid a snap rocks must NOT lie in 4 X 4 boxes
{49,50,51,52}x{49,50,51,52},….,{9,10,11,12}x{9,10,11,12},…, {1,2,3,4}x {1,2,3,4}
problem corresponds to 52 non-challenging rooks on a 52 x 52 board with 13 4 x 4 boxes blocked out along diagonal
thm 43: calculating rook polynomials theorem
let B be part of an n x n board and let s be one specified square of b. let C be the board B with S deleted and let D be B with the whole of S’s row and column deleted.
Then r_B(x) = r_C(x) + xr_B(x)
equivalent problem placing one rook on S or not
EXAMPLE: 3 x 3 Grid
[ ][x][x]
[x][ ][ ]
[ ][x][ ]
x means blacked out
[ ][x][x] [x][ ][ ] [ ][x][S] by deleting S: C [ ][x][x] [x][ ][ ] [ ][x ][x]
by deleting row and column of S:D
[ ][x]
[x][ ]
r_C(x)= 1+4x+4x^2 r_D(x)= 1+2x +x^2
so r_B= 1+5x+6x^2+x^3
(or B= C union D from splitting board into 2 pieces that do not share any row or column)
EXAMPLE: 4 x 4 Grid from B= C union D from splitting board into 2 pieces that do not share any row or column
1 2 3 4
a [C ][ x][C][ x]
b [ x ][ x][C][ x]
c [x ][D][ x][D]
d [x ][D][ x][D]
x means blacked out
r_B(x) = r_C(x)r_D(x) r_C(x)= 1 + 3x+ x^2 r_D(x)= 1 + 4x+ 2x^2
D= deleting rows completely blocked
2 4
c [ ][ ]
d [ ][ ]
C
1 3
a [ ][ ]
b [x][ ]
theorem 46:: for disjoint rows and columns
proof from disjoint Rows and columns meaning can’t challenge
example 48 :use of polynomials to find the number of ways of adding a fourth row of numbers 1 to 5 so that no repeats in any column
a b c d e [1 ][2][3][4][5] [2][4][5][3][1 ] [4][3][1 ][5][2] [ ][ ][ ][ ][ ]
as a rook problem:
(1)
1 2 3 4 5
a [x][x][ ][x][ ]
b [ ][x][x][x][s]
c [x][ ][x][ ][x]
d [ ][ ][x][x][x]
e [x][x][ ][ ][x]
by thm 43 and 46
choosing s, deleting twice and splitting:
(2)
1 2 3 4
a [x][x][ ][x]
b [ x][ ][x][s]
c [ ][ ][x][x]
d [x][x][ ][ ]
(3) from 2
a [x][x][Q]
c [P][P][x]
d [x][x][Q]
[Q] [P][P] [Q] (4) from 2
1 2 3 4 a [x][x][R][x] b [x][S][x][x] c [S][S][x][x] d [x][x][R][R]
[R][ x] [x][S]
[R][R] [S][S]
(5) from 1
1 2 3 4 5
a [x][x][ ][x][ ]
b [ ][x][x][x][x]
c [x][ ][x][s][x]
d [ ][ ][x][x][x]
e [x][x][ ][ ][x]
(6) from 5
1 2 3 5
a [x ][x][T][T]
b [U][x][x][x]
d [U][U][x][x]
e [x ][x ][T][x]
[T][T] [U][x]
[T][ x] [U][U]
(7) from 5
1 2 3 4 5
a [x ][x ][v][x][v]
b [w][x ][x][x][x]
c [x ][w][x][X][x]
d [w][w][x][x][x]
e [x ][x ][v][v][x]
[w][x ] [v][x][v] [x ][w] [v][v][x] [w][w] -------- r_5(x)= r_7(x) + xr_6(x) r_2(x)=r_4(x)+xr_3(x) r_1(x) = r_5(x) + xr_2(x) ----------- r_7(x)= (1+4x+3x^2)^2 = 1+8x+22x^2+24x^3 + 5x^4 r_6(x)= r_5(x)= r_4(x)= r_3(x)= r_2(x)= r_1(x)=
r_1(x)=
tabular approach is more efficient…
definition complement
if B is the unshaded part of an n x n board then the complement of B (overlineB) is given by the shaded part of the n xn board
example of board B and it's complement [x][x][ ][ ][x] [x][x][ ][ ][x] [ ][ ][x][x][x] [x][ ][x][x][ ] [ ][x][x][x][ ]
overline B is
[ ][ ][x][x][ ] [ ][ ][x][x][ ] [x][x][ ][ ][ ] [ ][x][ ][ ][x] [x][ ][ ][ ][x]
r_B(x) = 1 +10x + 35x^2 +50x^3 +26 x^4+4x^5
of complement is =1 +15x + 75x^2 +145x^3 + 96x^4+12x^5
(5! x 1) - (4!x10) - (3!x35) - (2!x50) - (1!x26) - (0!x4) = 12
thm 51: calculate the highest coefficient of the rook polynomial of the complement of B from the rook polynomial of B
Let B be part of an n × n board and let its rook polynomial be 1 + r1x + r2x^2 + · · · + rnx^n
Then the number of ways of placing n non-challenging rooks on Bline, the complement of B, is
sum from k=0 to n of
(−1)^k(n − k)!r_k
where r_0 = 1
ie coeff of required x __
notes???
pages example 48 , 40 ,7,8,9
snap problem and complements
complement of the reduced problem (52 non-challenging rooks on a 52 x 52 board with 13 4 x 4 boxes blocked out along diagonal)
52x52 board with only unshaded 13 4x4 on diagonal:
each 4 x 4 block has Rook polynomial p(x)= Σ from k=0 to 4 of [(4Ck)^2k!x^k] = 1+16x+72x^2+96x^3+24x^4
using theorem 46 repeatedly we see that r_B(x)= p(x)^13.
if p(x)^13 = Σ from k=0 to 52 of c_kx^k
then the number of possible deals with no snap= # ways of placing 52 rocks on the complement= Σ from k=0 to 52 of (-1)^k(52-k)!c_k
1.3 x 10^66, 52!= 8.1 x 10^67 sp probability of no snap os 0.016
hostess problem and complements
complement of the hostess problem board is
[ ][x][x][x][ ] [ ][ ][x][x][x] [x][ ][ ][x][x] [x][x][ ][ ][x] [x][x][x][ ][ ]
if we fill in the top right corner we get a 5 x 5 staircase. if we delete the row and column of the top right corner we get a 4 x 4 staircase. by thm 43:
r_B(x)= s_5(x) -xs_4(x)
s_5(x) = 1 + (9C1)x + (8C2)x^2 + (7C3)x^3 +(6C4)x^4 + (5c5)x^5
= 1 +9x + 28x^2 + 35x^3+15x^4 +x^5
s_4(x) = 1 + (8C1)x + (7C2)x^2 + (6C3)x^3 +(5C4)x^4 = 1+8x+21x^2+20x^3+5x^4
r_B(x)= 1 +10x +36x^2 + 56x^3 +35x^4 + 6x^5
thm 51 gives numbers solutions for the main step of the hostess problem = c_5(Bcomplement) = 5! x1 -4!x10 + 3!x36 -2!x56 - 1!x35 -0!x6
and this works out as 13, earlier answer
staircase
5 by 5 grid rook problem
nxn general
[ ][x][x][x][x] [ ][ ][x][x][x] [x][ ][ ][x][x] [x][x][ ][ ][x] [x][x][x][ ][ ]
this has 9 unblock squares arranged so that rocks placed on the staircase can only attack each other if they are adjacent.
thus the number of ways of placing k rocks is the same as the number of subsets of size k in {1,..,9} with no adjacent entries.
previous examples show this is ({10-k}C{k})
so the root polynomial for the 5 x 5 staircase is Σ from k=0 to 5 of [({10-k}C{k})x^k]
for the nxn staircase
Σ from k=0 to n of [({2n-k}C{k})x^k]= s_n(x)
lemma: nxn board with rows and columns with number of ways of placing |S_
let X= {x_1,..,x_m} b a set of squares on an n x n board.
Let S_X be the set of ways of placing n rocks in the board such that there is a rook at each position x_i and no two rooks challenge each other. Then
a) if there is a row containing two x_i’s or a column containing two x_i’s, then S_X= empty set and |S_X|=0
b) otherwise we have |s_x| = (n-m)!
