Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

MAS334 Combinatorics > chapter 3: rook polynomials > Flashcards

chapter 3: rook polynomials Flashcards

1
Q

Rook

A

a rook challenges another piece if it’s in the same row or column

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

EXAMPLE: ways of placing on a 3 by 3 board

1,2 and 3

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q 
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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

definition Rook polynomial

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

reducing problems to Rooks

A

for example assignments permutations with shaded boxes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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 ,..

A

Rook polynomial grid with shaded squares

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

shaded squares Rook polynomials

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

EXAMPLE: hostess problem

5 couples sat alternating man and woman such that not next to partner

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

thm 43: calculating rook polynomials theorem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

EXAMPLE: 3 x 3 Grid
[ ][x][x]
[x][ ][ ]
[ ][x][ ]

x means blacked out

A 
[  ][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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q 
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

A 
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][ ]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

theorem 46:: for disjoint rows and columns

A

proof from disjoint Rows and columns meaning can’t challenge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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]
[   ][  ][  ][  ][  ]
A 
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…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

definition complement

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q 
example of board B and it's complement
[x][x][  ][  ][x]
[x][x][  ][  ][x]
[  ][  ][x][x][x]
[x][  ][x][x][  ]
[  ][x][x][x][  ]
A

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

17
Q

thm 51: calculate the highest coefficient of the rook polynomial of the complement of B from the rook polynomial of B

A

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 __

18
Q

notes???

A

pages example 48 , 40 ,7,8,9

19
Q

snap problem and complements

A

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

20
Q

hostess problem and complements

A

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

21
Q

staircase
5 by 5 grid rook problem

nxn general

A 
[  ][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)

22
Q

lemma: nxn board with rows and columns with number of ways of placing |S_

A

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)!

MAS334 Combinatorics (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions