{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Warning" -1 7 1 
{CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 2 2 2 2 2 1 1 1 3 1 }1 1 0 
0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 
0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 
0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 75 "This maple work sheet sets
 up some procedures relating to rook polynomials," }}{PARA 0 "" 0 "" 
{TEXT -1 65 "including complement boards and calculations of rook poly
nomials." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(combinat):
 " }{TEXT -1 0 "" }}{PARA 7 "" 1 "" {TEXT -1 67 "Warning, the protecte
d name Chi has been redefined and unprotected\n" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
158 "rook_attack := proc (L1, L2, n) local i, j, ans; if L1[1] = L2[1]
 then RETURN(true) end if; if L1[2] = L2[2] then RETURN(true) end if; \+
RETURN(false) end proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,rook_att
ackGf*6%%#L1G%#L2G%\"nG6%%\"iG%\"jG%$ansG6\"F.C%@$/&9$6#\"\"\"&9%F4-%'
RETURNG6#%%trueG@$/&F36#\"\"#&F7F?F8-F96#%&falseGF.F.F." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 251 "array_board:=proc(F,n)\n#returns t
he 0,`x` matrix of the \n#forbidden squares from F on an nxn board\nlo
cal i,j,A;\nA:=array(1..n,1..n):\nfor i from 1 to n do\nfor j from 1 t
o n do\nA[i,j]:=0;\nif member([i,j],F) then A[i,j]:=`x`; fi;\nod;\nod;
\nprint(A);\nend; \n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,array_board
Gf*6$%\"FG%\"nG6%%\"iG%\"jG%\"AG6\"F-C%>8&-%&arrayG6$;\"\"\"9%F4?(8$F5
F5F6%%trueG?(8%F5F5F6F9C$>&F06$F8F;\"\"!@$-%'memberG6$7$F8F;9$>F>%\"xG
-%&printG6#F0F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 236 "arr
ay_rooks:=proc(L,n)\n#returns the 0,`R` matrix of the rooks at L\n#on \+
an nxn board\nlocal i,j,A;\nA:=array(1..n,1..n):\nfor i from 1 to n do
\nfor j from 1 to n do\nA[i,j]:=0;\nif member([i,j],L) then A[i,j]:=`R
`; fi;\nod;\nod;\nprint(A);\nend; \n" }}{PARA 12 "" 1 "" {XPPMATH 20 "
6#>%,array_rooksGf*6$%\"LG%\"nG6%%\"iG%\"jG%\"AG6\"F-C%>8&-%&arrayG6$;
\"\"\"9%F4?(8$F5F5F6%%trueG?(8%F5F5F6F9C$>&F06$F8F;\"\"!@$-%'memberG6$
7$F8F;9$>F>%\"RG-%&printG6#F0F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 248 "complement_board:=proc(F,n)\n#computes the list of a
llowed squares\n#where F is the list of forbidden squares\nlocal i,j,x
,L;\nL:=[];\nfor i from 1 to n do\nfor j from 1 to n do\nif not(member
([i,j],F)) then L:=[op(L),[i,j]]: fi;\nod;\nod;\nRETURN(L);\nend; \n" 
}}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%1complement_boardGf*6$%\"FG%\"nG6&
%\"iG%\"jG%\"xG%\"LG6\"F.C%>8'7\"?(8$\"\"\"F59%%%trueG?(8%F5F5F6F7@$4-
%'memberG6$7$F4F99$>F17$-%#opG6#F1F?-%'RETURNGFEF.F.F." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 542 "non_attacking_rooks_pos:=proc(F,k,
n)\n#returns all possible positions\n#for k non-attacking rooks \n#on \+
an nxn board with forbidden positions\n#listed in (the list of lists) \+
F\nlocal i,j,ans,cols,R,pos,F0,F1,F2,m,P,x,stop0,is;\nP:=permute(n,n);
\nF0:=F; \npos:=[];\nif k=1 then RETURN(complement_board(F0,n)); fi;\n
for x in P do\nstop0:=0;\nR:=choose(n,k);\nfor is in R do\nstop0:=0;\n
for i in is do\nif member([i,x[i]],F0) then stop0:=1; fi; \nod;\nif st
op0=0 then pos:=[op(pos),[seq([i,x[i]],i=is)]]; fi;\nod;\nod;\nRETURN(
convert(convert(pos,set),list));\nend; \n" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%8non_attacking_rooks_posGf*6%%\"FG%\"kG%\"nG60%\"iG%
\"jG%$ansG%%colsG%\"RG%$posG%#F0G%#F1G%#F2G%\"mG%\"PG%\"xG%&stop0G%#is
G6\"F9C(>8.-%(permuteG6$9&F@>8*9$>8)7\"@$/9%\"\"\"-%'RETURNG6#-%1compl
ement_boardG6$FBF@?&8/F<%%trueGC%>80\"\"!>8(-%'chooseG6$F@FI?&81FYFSC%
>FVFW?&8$FhnFS@$-%'memberG6$7$F\\o&FR6#F\\oFB>FVFJ@$/FVFW>FE7$-%#opG6#
FE7#-%$seqG6$Fao/F\\oFhn-FL6#-%(convertG6$-Fdp6$FE%$setG%%listGF9F9F9
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 262 "rook_polynomial:=proc(
F,n,x)\n#returns the rook polynomial of the nxn\n#board with forbidden
 positions F\n#written as a list of lists of coordinated for\n#the for
bidden squares\nlocal i,a,p;\np:=1+add(nops(non_attacking_rooks_pos(F,
i,n))*x^i,i=1..n);\nRETURN(p);\nend; \n" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%0rook_polynomialGf*6%%\"FG%\"nG%\"xG6%%\"iG%\"aG%\"pG6\"F.C$>8
&,&\"\"\"F3-%$addG6$*&-%%nopsG6#-%8non_attacking_rooks_posG6%9$8$9%F3)
9&F?F3/F?;F3F@F3-%'RETURNG6#F1F.F.F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 86 "Here we apply some of the procedures to examples taken from an \+
old Combinatorics exam." }}{PARA 0 "" 0 "" {TEXT -1 58 "The first one \+
calculates the rook polynomial of a board B." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 95 "B:=[[1,2],[1,3],[2,2],[2,3],[3,1],[3,4],[3,5],[4
,1],[4,4],[4,5],[5,4]]; rook_polynomial(B,5,x);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"BG7-7$\"\"\"\"\"#7$F'\"\"$7$F(F(7$F(F*7$F*F'7$F*\"
\"%7$F*\"\"&7$F/F'7$F/F/7$F/F17$F1F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#,.\"\"\"F$*&\"#9F$%\"xGF$F$*&\"#kF$)F'\"\"#F$F$*&\"$7\"F$)F'\"\"$F$F
$*&\"#oF$)F'\"\"%F$F$*&\"\")F$)F'\"\"&F$F$" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 67 "Along the way, we needed the rook polynomial of the full \+
2x3 board:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "C:=[[3,1],[3,
2],[3,3]]; rook_polynomial(C,3,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
>%\"CG7%7$\"\"$\"\"\"7$F'\"\"#7$F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#,(\"\"\"F$*&\"\"'F$%\"xGF$F$*&F&F$)F'\"\"#F$F$" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 31 "And here's another calculation." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 61 "B:=[[2,4],[3,4],[4,1],[4,2],[4,3]];\nrook
_polynomial(B,4,x); \n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG7'7$\"
\"#\"\"%7$\"\"$F(7$F(\"\"\"7$F(F'7$F(F*" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#,,\"\"\"F$*&\"#6F$%\"xGF$F$*&\"#LF$)F'\"\"#F$F$*&\"#IF$)F'\"\"$F
$F$*&\"\"'F$)F'\"\"%F$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}}{MARK "14 2 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 0 1 2 33 1 1 }