Rook polynomials

This worksheet shows how to use maple to compute rook polynomials. The boards use "matrix notation".

>

> with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>

>

> rook_attack:=proc(L1,L2,n)
#returns true of the rook at L1 attacks
#the rook at L2 on an nxn board
local i,j,ans;
if L1[1]=L2[1] then RETURN(`true`); fi:
if L1[2]=L2[2] then RETURN(`true`); fi:
RETURN(`false`):
end;

rook_attack := proc (L1, L2, n) local i, j, ans; if...

>

> array_board:=proc(F,n)
#returns the 0,`x` matrix of the
#forbidden squares from F on an nxn board
local i,j,A;
A:=array(1..n,1..n):
for i from 1 to n do
for j from 1 to n do
A[i,j]:=0;
if member([i,j],F) then A[i,j]:=`x`; fi;
od;
od;
print(A);
end;

array_board := proc (F, n) local i, j, A; A := arra...
array_board := proc (F, n) local i, j, A; A := arra...

>

> array_rooks:=proc(L,n)
#returns the 0,`R` matrix of the rooks at L
#on an nxn board
local i,j,A;
A:=array(1..n,1..n):
for i from 1 to n do
for j from 1 to n do
A[i,j]:=0;
if member([i,j],L) then A[i,j]:=`R`; fi;
od;
od;
print(A);
end;

array_rooks := proc (L, n) local i, j, A; A := arra...
array_rooks := proc (L, n) local i, j, A; A := arra...

>

> complement_board:=proc(F,n)
#computes the list of allows squares
#where F is the list of forbidden squares
local i,j,x,L;
L:=[];
for i from 1 to n do
for j from 1 to n do
if not(member([i,j],F)) then L:=[op(L),[i,j]]: fi;
od;
od;
RETURN(L);
end;

complement_board := proc (F, n) local i, j, x, L; L...
complement_board := proc (F, n) local i, j, x, L; L...

>

> non_attacking_rooks_pos:=proc(F,k,n)
#returns all possible positions
#for k non-attacking rooks
#on an nxn board with forbidden positions
#listed in (the list of lists) F
local i,j,ans,cols,R,pos,F0,F1,F2,m,P,x,stop0,is;
P:=permute(n,n);
F0:=F;
pos:=[];
if k=1 then RETURN(complement_board(F0,n)); fi;
for x in P do
stop0:=0;
R:=choose(n,k);
for is in R do
stop0:=0;
for i in is do
if member([i,x[i]],F0) then stop0:=1; fi;
od;
if stop0=0 then pos:=[op(pos),[seq([i,x[i]],i=is)]]; fi;
od;
od;
RETURN(convert(convert(pos,set),list));
end;

non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...
non_attacking_rooks_pos := proc (F, k, n) local i, ...

>

> rook_polynomial:=proc(F,n,x)
#returns the rook polynomial of the nxn
#board with forbidden positions F
#written as a list of lists of coordinated for
#the forbidden squares
local i,a,p;
p:=1+add(nops(non_attacking_rooks_pos(F,i,n))*x^i,i=1..n);
RETURN(p);
end;

rook_polynomial := proc (F, n, x) local i, a, p; p ...

>

Here's the board, with a rook at (1,1) and (2,3).

> array_rooks([[1,1],[2,3]],5);

matrix([[R, 0, 0, 0, 0], [0, 0, R, 0, 0], [0, 0, 0,...

Does the rook at (1,1) attack the rook at (2,3)?

> rook_attack([1,1],[2,3],5);
rook_attack([1,1],[1,3],5);

false

true

>

>

Here's the list of positions where there isn't a rook.

> complement_board([[1,1],[2,3]],3);

[[1, 2], [1, 3], [2, 1], [2, 2], [3, 1], [3, 2], [3...

Here's an example. All the x'ed out positions mean that the corresponding position is "forbidden" - no rook can land or cross over it. What is the rook polynomial of this board with forbidden positions?

> B:=[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,5],[3,4],[4,3],[4,5],[5,1],[5,2],[5,3],[5,4],[5,5]];
L:=non_attacking_rooks_pos(B,2,5):
nops(L);
array_board(B,5);
rook_polynomial(B,5,x);

B := [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2...

23

matrix([[x, x, x, x, 0], [x, x, x, 0, x], [0, 0, 0,...

1+9*x+23*x^2+18*x^3+4*x^4

>

>

Here's another example. All the x'ed out positions mean that the corresponding position is "forbidden" - no rook can land or cross over it. What is the list of all possible ways 5 non-attacking rooks can be placed on this board with forbidden positions? We only list the first four.

> array_board([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5);
rook_polynomial([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5,x);
L:=non_attacking_rooks_pos([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5,5):
nops(L);
for i from 1 to 4 do
array_rooks(L[i],5);
od;

matrix([[0, x, x, 0, 0], [x, 0, x, 0, 0], [0, x, 0,...

1+17*x+92*x^2+187*x^3+128*x^4+18*x^5

18

matrix([[R, 0, 0, 0, 0], [0, R, 0, 0, 0], [0, 0, R,...

matrix([[0, 0, 0, R, 0], [0, R, 0, 0, 0], [0, 0, R,...

matrix([[0, 0, 0, R, 0], [0, R, 0, 0, 0], [0, 0, R,...

matrix([[0, 0, 0, R, 0], [0, R, 0, 0, 0], [R, 0, 0,...

>

What about the rook polynomials of the 2x2, 3x3, and 4x4 boards with no forbidden positions?

> rook_polynomial([],2,x);
rook_polynomial([],3,x);
rook_polynomial([],4,x);

1+4*x+2*x^2

1+9*x+18*x^2+6*x^3

1+16*x+72*x^2+96*x^3+24*x^4

>

>

>

>


Last updated 5-1-2003 by wdj