###################################################################### ##ChessWalks: Save this file as ChessWalks # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read ChessWalks # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: May 17, 2011 print(`Created: May 17, 2011`): print(` This is ChessWalks `): print(`It generated the article `): print(`In How Many Ways Can The Chess Pieces Walk n steps, staying on the board?`): print(`by Shalosh B. Ekhad`): print(`published in`): print(`http://www.math.rutgers.edu/~zeilberg/pj.html .`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the CHECKING procedures type ezraCheck();,`): print(` for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(``): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezraCheck:=proc() if args=NULL then print(`The checking procedures are: CheckOneDWalks, CheckTwoDWalks`): print(` OneDWalksNumber,OneDWalksSet, TwoDWalksNumber,TwoDWalksSet, `): else ezra(args): fi: end: ezraChess:=proc() if args=NULL then print(`The Chess procedures are: `): print(` BishopWalksA, KingWalksA, KnightWalksA, QueenWalksA, RookWalksA`): print(` BishopWalksB, KingWalksB, KnightWalksB, QueenWalksB, RookWalksB`): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: AsyRat, ChessStory `): print(` OneDWalks, OneDWalksA, OneDWalksB, TwoDWalks, , TwoDWalksA `): print(` TwoDWalksB `): elif nops([args])=1 and op(1,[args])=AsyRat then print(`AsyRat(R,t): the asymptotics of the coefficients of the`): print(`Maclaurin expansion of the rational function R in`): print(`the variable t. For example, try:`): print(`AsyRat((1+t)/(1-5*t+6*t^2),t,n);`): elif nops([args])=1 and op(1,[args])=BishopWalksA then print(`BishopWalksA(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Bishop can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and ending anywhere on the board. `): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Bishop, do:`): print(`BishopWalksA(8,8,3,1,t);`): elif nops([args])=1 and op(1,[args])=BishopWalksB then print(`BishopWalksB(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Bishop can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and returning to it.`): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Bishop, do:`): print(`BishopWalksB(8,8,3,1,t);`): elif nops([args])=1 and op(1,[args])=CheckOneDWalks then print(`CheckOneDWalks(A,i,S,N): checks the first N terms of`): print(`OneDWalks(A,i,S,t)`): print(`For example, try:`): print(`CheckOneDWalks(3,1,{1,-1},10);`): elif nops([args])=1 and op(1,[args])=CheckTwoDWalks then print(`CheckTwoDWalks(A,B,i1,j1,S,N): checks the first N terms of`): print(`TwoDWalks(A,B,i1,j1,S,t)`): print(`For example, try:`): print(`CheckOneDWalks(3,3,1,1,{[0,-1],[0,1],[1,0],[-1,0]},10);`): elif nops([args])=1 and op(1,[args])=ChessStory then print(`ChessStory(A,B,n0): the procedure that generates a article`): print(`about the generating functions for the number of ways`): print(`of walking on an A by B board.`): print(`For each piece it also spits out the first n0 terms (for OEIS)`): print(`Try: `): print(`ChessStory(5,5,30); `): elif nops([args])=1 and op(1,[args])=KingWalksA then print(`KingWalksA(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a King can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1] , and ending anywhere on the board.`): print(` For example, for traditional`): print(`Chess, and the traditional starting point of a King, do:`): print(`KingWalksA(8,8,5,1,t);`): elif nops([args])=1 and op(1,[args])=KingWalksB then print(`KingWalksB(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a King can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and returning back to it.`): print(` For example, for traditional`): print(`Chess, and the traditional starting point of a King, do:`): print(`KingWalksB(8,8,5,1,t);`): elif nops([args])=1 and op(1,[args])=KnightWalksA then print(`KnightWalksA(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Knight can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1] , and ending anywhere on the board. `): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Knight, do:`): print(`KnightWalksA(8,8,1,3,t);`): elif nops([args])=1 and op(1,[args])=KnightWalksB then print(`KnightWalksB(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Knight can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and returning back to it.`): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Knight, do:`): print(`KnightWalksB(8,8,1,3,t);`): elif nops([args])=1 and op(1,[args])=OneDWalksA then print(`OneDWalksA(A,i,S,t): `): print(`the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from i all that time staying`): print(`in the discrete line segment`): print(`between 1 and A (i.e. without falling off the cliif),`): print(`using the set of steps S (a set of integers) `): print(`For example, try:`): print(` OneDWalksA(3,1,{1,-1},t); `): elif nops([args])=1 and op(1,[args])=OneDWalksB then print(`OneDWalksB(A,i,S,t): `): print(`the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from i back to i, in the discrete line segment`): print(`between 1 and A,`): print(`using the set of steps S (a set of integers) `): print(`For example, try:`): print(` OneDWalksB(3,1,{1,-1},t); `): elif nops([args])=1 and op(1,[args])=OneDWalksNumber then print(`OneDWalksNumber(A,i,j,S,n): The number of walks in [1,A] of length n`): print(`starting at i and ending at j, with set of steps S`): print(`For example, try:`): print(`OneDWalksSet(4,1,1,{1,-1},3);`): elif nops([args])=1 and op(1,[args])=OneDWalksSet then print(`OneDWalksSet(A,i,j,S,n): The set of walks in [1,A] of length n`): print(`starting at i and ending at j, with set of steps S`): print(`For example, try:`): print(`OneDWalksSet(4,1,1,{1,-1},3);`): elif nops([args])=1 and op(1,[args])=OneDWalks then print(`OneDWalks(A,i,S,t): the list of size A whose j-th`): print(`component is the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from i to j, in the discrete line segment`): print(`between 1 and A,`): print(`using the set of steps S (a set of integers) `): print(`For example, try:`): print(` OneDWalks(3,1,{1,-1},t); `): elif nops([args])=1 and op(1,[args])=QueenWalksA then print(`QueenWalksA(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Queen can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and ending anywhere on the board.`): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Queeen, do:`): print(`QueenWalksA(8,8,4,1,t);`): elif nops([args])=1 and op(1,[args])=QueenWalksB then print(`QueenWalksB(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Queen can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and returning to it`): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Queeen, do:`): print(`QueenWalksB(8,8,4,1,t);`): elif nops([args])=1 and op(1,[args])=RookWalksA then print(`RookWalksA(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Rook can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and ending anywhere on the board. `): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Rook, do:`): print(`RookWalksA(8,8,1,1,t);`): elif nops([args])=1 and op(1,[args])=RookWalksB then print(`RookWalksB(A,B,i1,j1,t): The generating function `): print(`(a certain rational function) whose coeff. of t^n is`): print(`the number of ways a Rook can walk n steps in an A by B chessboard`): print(`starting at location [i1,j1], and returning to it.`): print(`For example, for traditional`): print(`Chess, and the traditional starting point of a Rook, do:`): print(`RookWalksB(8,8,1,1,t);`): elif nops([args])=1 and op(1,[args])=TwoDWalks then print(`TwoDWalks(A,B,i1,j1,S,t): the double-list of size A by B `): print(`let's call it L, such that`): print(`whose L[i2][j2] is`): print(`the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from [i1,j1] to [i2,j2], in the A by B Chessboard`): print(`using the set of steps S (a set of pairs of integers) `): print(`For example, try:`): print(`TwoDWalks(3,3,1,1,{[1,0],[-1,0],[0,-1],[0,1]},t);`): elif nops([args])=1 and op(1,[args])=TwoDWalksA then print(`TwoDWalksA(A,B,i1,j1,S,t): `): print(`the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from [i1,j1] and still staying `): print(` in the A by B Chessboard [1,A]x[1,B]`): print(`using the set of steps S (a set of pairs of integers) `): print(`For example, try:`): print(`TwoDWalksA(3,3,2,2,{[1,0],[-1,0],[0,-1],[0,1]},t);`): elif nops([args])=1 and op(1,[args])=TwoDWalksB then print(`TwoDWalksB(A,B,i1,j1,S,t): `): print(`the generating function in t (a rational function)`): print(`whose coeff. of t^n is the number of ways of walking `): print(`exactly n steps from [i1,j1] back to `): print(` [i1,j1], in the A by B Chessboard [1,A]x[1,B]`): print(`using the set of steps S (a set of pairs of integers) `): print(`For example, try:`): print(`TwoDWalksB(3,3,1,1,{[1,0],[-1,0],[0,-1],[0,1]},t);`): elif nops([args])=1 and op(1,[args])=TwoDWalksSet then print(`TwoDWalksSet(A,B,i1,j1,i2,j2,S,n): The set of walks in [1,A]x[1,B]`): print(`of length n`): print(`starting at [1i,j1] and ending at [i2,j2]`): print(`For example, try:`): print(`TwoDWalksSet(4,4,1,1,1,1,{[0,1],[0,-1],[1,0],[1,-0]},4):`): else print(`There is no ezra for`,args): fi: end: #AsyRat(R,t): the asymptotics of the coefficients of the #Maclaurin expansion of the rational function R in #the variable t. For example, try: #AsyRat((1+t)/(1-5*t+6*t^2),t,n); AsyRat:=proc(R,t,n) local N1,D1,lu,i,aluf,si,muam,halev,A,gu,ku: Digits:=30: N1:=numer(R): D1:=denom(R): lu:=[fsolve(D1,t)]: aluf:=lu[1]: si:=abs(lu[1]): for i from 2 to nops(lu) do muam:=lu[i]: halev:=abs(muam): if halev10^(-10) then RETURN(FAIL): else RETURN(gu): fi: end: #OneDWalks(A,i,S,t): the list of size A whose j-th #component is the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from i to j, in the discrete line segment #between 1 and A, #using the set of steps S (a set of integers) #For example, try: #OneDWalks(3,1,{1,-1},t); OneDWalks:=proc(A,i,S,t) local eq,var,j,x,eq1,s: eq:={}: var:={}: for j from 1 to A do var:=var union {x[j]}: if j=i then eq1:=x[j]-1: else eq1:=x[j]: fi: for s in S do if j-s>=1 and j-s<=A then eq1:=eq1-t*x[j-s]: fi: od: eq:=eq union {eq1}: od: var:=solve(eq,var): [seq(normal(subs(var,x[j])),j=1..A)]: end: #OneDWalksA(A,i,S,t): #the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from i staying in the discrete line segment #between 1 and A, #using the set of steps S (a set of integers) #For example, try: #OneDWalksA(3,1,{1,-1},t); OneDWalksA:=proc(A,i,S,t) local gu,i1,j1: normal(convert(OneDWalks(A,i,S,t),`+`)): end: #OneDWalksB(A,i,S,t): #the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from i back to i, in the discrete line segment #between 1 and A, #using the set of steps S (a set of integers) #For example, try: #OneDWalksB(3,1,{1,-1},t); OneDWalksB:=proc(A,i,S,t): OneDWalks(A,i,S,t)[i]: end: #TwoDWalks(A,B,i1,j1,S,t): the double-list of size A by B #let's call it L, such that #whose L[i2][j2] is #the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from [i1,j1] to [i2,j2], in the A by B Chessboard #using the set of steps S (a set of pairs of integers) #For example, try: #TwoDWalks(3,3,1,1,{[1,0],[-1,0],[0,-1],[0,1]},t); TwoDWalks:=proc(A,B,i1,j1,S,t) local eq,var,i2,j2,x,eq1,s: eq:={}: var:={}: for i2 from 1 to A do for j2 from 1 to B do var:=var union {x[i2,j2]}: if i2=i1 and j2=j1 then eq1:=x[i2,j2]-1: else eq1:=x[i2,j2]: fi: for s in S do if i2-s[1]>=1 and i2-s[1]<=A and j2-s[2]>=1 and j2-s[2]<=B then eq1:=eq1-t*x[i2-s[1],j2-s[2]]: fi: od: eq:=eq union {eq1}: od: od: var:=solve(eq,var): [seq([seq(normal(subs(var,x[i2,j2])),j2=1..B)],i2=1..A)]: end: #TwoDWalksB(A,B,i1,j1,S,t): #the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from [i1,j1] back to [i1,j1], in the A by B Chessboard #using the set of steps S (a set of pairs of integers) #For example, try: #TwoDWalksB(3,3,1,1,{[1,0],[-1,0],[0,-1],[0,1]},t); TwoDWalksB:=proc(A,B,i1,j1,S,t): TwoDWalks(A,B,i1,j1,S,t)[i1][j1]: end: #TwoDWalksA(A,B,i1,j1,S,t): #the generating function in t (a rational function) #whose coeff. of t^n is the number of ways of walking #exactly n steps from [i1,j1] staying in [1,A]x[1,B], #using the set of steps S (a set of pairs of integers) #For example, try: #TwoDWalksA(3,3,1,1,{[1,0],[-1,0],[0,-1],[0,1]},t); TwoDWalksA:=proc(A,B,i1,j1,S,t) local gu,i2,j2: gu:=TwoDWalks(A,B,i1,j1,S,t): normal(add(add(gu[i2][j2],j2=1..nops(gu[i2])),i2=1..nops(gu))): end: #OneDWalksSet(A,i,j,S,n): The set of walks in [1,A] of length n #starting at i and ending at j #For example, try: #OneDWalksSet(4,1,1,{1,-1},4): OneDWalksSet:=proc(A,i,j,S,n) local gu,lu,s,lu1: option remember: if n=0 then if j=i then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for s in S do if j-s>=1 and j-s<=A then lu:=OneDWalksSet(A,i,j-s,S,n-1): gu:=gu union {seq([op(lu1),s], lu1 in lu)} fi: od: gu: end: #OneDWalksNumber(A,i,j,S,n): The number of walks in [1,A] of length n #starting at i and ending at j #For example, try: #OneDWalksNumber(4,1,1,{1,-1},4): OneDWalksNumber:=proc(A,i,j,S,n) local gu,s: option remember: if n=0 then if j=i then RETURN(1): else RETURN(0): fi: fi: gu:=0: for s in S do if j-s>=1 and j-s<=A then gu:=gu+OneDWalksNumber(A,i,j-s,S,n-1): fi: od: gu: end: #TwoDWalksSet(A,B,i1,j1,i2,j2,S,n): The set of walks in [1,A]x[1,B] #of length n #starting at [1i,j1] and ending at [i2,j2] #For example, try: #TwoDWalksSet(4,4,1,1,1,1,{[0,1],[0,-1],[1,0],[1,-0]},4): TwoDWalksSet:=proc(A,B,i1,j1,i2,j2,S,n) local gu,lu,s,lu1: option remember: if n=0 then if i2=i1 and j2=j1 then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for s in S do if i2-s[1]>=1 and i2-s[1]<=A and j2-s[2]>=1 and j2-s[2]<=B then lu:=TwoDWalksSet(A,B,i1,j1,i2-s[1],j2-s[2],S,n-1): gu:=gu union {seq([op(lu1),s], lu1 in lu)} fi: od: gu: end: #TwoDWalksNumber(A,B,i1,j1,i2,j2,S,n): The number of walks in [1,A]x[1,B] #of length n #starting at [1i,j1] and ending at [i2,j2] #For example, try: #TwoDWalksNumber(4,4,1,1,1,1,{[0,1],[0,-1],[1,0],[1,-0]},4): TwoDWalksNumber:=proc(A,B,i1,j1,i2,j2,S,n) local gu,s: option remember: if n=0 then if i2=i1 and j2=j1 then RETURN(1): else RETURN(0): fi: fi: gu:=0: for s in S do if i2-s[1]>=1 and i2-s[1]<=A and j2-s[2]>=1 and j2-s[2]<=B then gu:=gu+TwoDWalksNumber(A,B,i1,j1,i2-s[1],j2-s[2],S,n-1): fi: od: gu: end: #CheckOneDWalks(A,i,S,N): checks the first N terms of #OneDWalks(A,i,S,t) #For example, try: #CheckOneDWalks(3,1,{1,-1},10); CheckOneDWalks:=proc(A,i,S,N) local lu,lu1,t,j,n1: lu:=OneDWalks(A,i,S,t): for j from 1 to A do lu1:=lu[j]: lu1:=taylor(lu1,t=0,N+1): if {seq(evalb(coeff(lu1,t,n1)=OneDWalksNumber(A,i,j,S,n1)),n1=0..N)}<>{true} then RETURN(false): fi: od: true: end: #CheckTwoDWalks(A,B,i1,j1,S,N): checks the first N terms of #TwoDWalks(A,B,i1,j1,S,t) #For example, try: #CheckOneDWalks(3,3,1,1,{[0,-1],[0,1],[1,0],[-1,0]},10); CheckTwoDWalks:=proc(A,B,i1,j1,S,N) local lu,lu1,t,i2,j2,n1: lu:=TwoDWalks(A,B,i1,j1,S,t): for i2 from 1 to A do for j2 from 1 to B do lu1:=lu[i2][j2]: lu1:=taylor(lu1,t=0,N+1): if {seq(evalb(coeff(lu1,t,n1)=TwoDWalksNumber(A,B,i1,j1,i2,j2,S,n1)),n1=0..N)}<>{true} then RETURN(false): fi: od: od: true: end: ###Start Chess Pieces Procedures ##Start going back to the initial location #KingWalksB(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a King can walk in an A by B chessboard #starting and ending at location [i1,j1]. For example, for traditional #Chess, and the traditional starting point of a King, do: #KingWalksB(8,8,1,5,t); KingWalksB:=proc(A,B,i1,j1,t) local S: S:={[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]}: TwoDWalksB(A,B,i1,j1,S,t): end: #KnightWalksB(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Knight can walk in an A by B chessboard #starting and ending at location [i1,j1]. For example, for traditional #Chess, and the traditional starting point of a Knight, do: #KnightWalksB(8,8,1,2,t); KnightWalksB:=proc(A,B,i1,j1,t) local S: S:={[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[-2,-1],[2,-1]}: TwoDWalksB(A,B,i1,j1,S,t): end: #RookWalksB(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Rook can walk in an A by B chessboard #starting and ending at location [i1,j1]. For example, for traditional #Chess, and the traditional starting point of a Rook, do: #RookWalksB(8,8,1,1,t); RookWalksB:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,0],i=1..A-1),seq([-i,0],i=1..A-1), seq([0,i],i=1..B-1), seq([0,-i],i=1..B-1)}: TwoDWalksB(A,B,i1,j1,S,t): end: #BishopWalksB(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Bishop can walk in an A by B chessboard #starting and ending at location [i1,j1]. For example, for traditional #Chess, and the traditional starting point of a Bishop, do: #BishopWalksB(8,8,3,1,t); BishopWalksB:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,i],i=1..min(A-1,B-1)), seq([i,-i],i=1..min(A-1,B-1)), seq([-i,i],i=1..min(A-1,B-1)), seq([-i,-i],i=1..min(A-1,B-1))}: TwoDWalksB(A,B,i1,j1,S,t): end: #QueenWalksB(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Queen can walk in an A by B chessboard #starting and ending at location [i1,j1]. For example, for traditional #Chess, and the traditional starting point of a Queen, do: #QueenWalksB(8,8,4,1,t); QueenWalksB:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,i],i=1..min(A-1,B-1)), seq([i,-i],i=1..min(A-1,B-1)), seq([-i,i],i=1..min(A-1,B-1)), seq([-i,-i],i=1..min(A-1,B-1))}: S:=S union {seq([i,0],i=1..A-1),seq([-i,0],i=1..A-1), seq([0,i],i=1..B-1), seq([0,-i],i=1..B-1)}: TwoDWalksB(A,B,i1,j1,S,t): end: ##End going back to the initial location ##Start ending wherever #KingWalksA(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a King can walk in an A by B chessboard #starting at location [i1,j1] and ending anywhere # For example, for traditional #Chess, and the traditional starting point of a King, do: #KingWalksA(8,8,1,5,t); KingWalksA:=proc(A,B,i1,j1,t) local S: S:={[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]}: TwoDWalksA(A,B,i1,j1,S,t): end: #KnightWalksA(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Knight can walk in an A by B chessboard #starting at location [i1,j1] and ending anywhere. #For example, for traditional #Chess, and the traditional starting point of a Knight, do: #KnightWalksA(8,8,1,2,t); KnightWalksA:=proc(A,B,i1,j1,t) local S: S:={[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[-2,-1],[2,-1]}: TwoDWalksA(A,B,i1,j1,S,t): end: #RookWalksA(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Rook can walk in an A by B chessboard #starting at location [i1,j1] and ending anywhere. #For example, for traditional #Chess, and the traditional starting point of a Rook, do: #RookWalksA(8,8,1,1,t); RookWalksA:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,0],i=1..A-1),seq([-i,0],i=1..A-1), seq([0,i],i=1..B-1), seq([0,-i],i=1..B-1)}: TwoDWalksA(A,B,i1,j1,S,t): end: #BishopWalksA(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Bishop can walk in an A by B chessboard #starting at location [i1,j1] and ending anywhere. #For example, for traditional #Chess, and the traditional starting point of a Bishop, do: #BishopWalksA(8,8,3,1,t); BishopWalksA:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,i],i=1..min(A-1,B-1)), seq([i,-i],i=1..min(A-1,B-1)), seq([-i,i],i=1..min(A-1,B-1)), seq([-i,-i],i=1..min(A-1,B-1))}: TwoDWalksA(A,B,i1,j1,S,t): end: #QueenWalksA(A,B,i1,j1,t): The generating function #(a certain rational function) whose coeff. of t^n is #the number of ways a Queen can walk in an A by B chessboard #starting at location [i1,j1] and ending anywhere. #For example, for traditional #Chess, and the traditional starting point of a Queen, do: #QueenWalksA(8,8,4,1,t); QueenWalksA:=proc(A,B,i1,j1,t) local S,i: S:={seq([i,i],i=1..min(A-1,B-1)), seq([i,-i],i=1..min(A-1,B-1)), seq([-i,i],i=1..min(A-1,B-1)), seq([-i,-i],i=1..min(A-1,B-1))}: S:=S union {seq([i,0],i=1..A-1),seq([-i,0],i=1..A-1), seq([0,i],i=1..B-1), seq([0,-i],i=1..B-1)}: TwoDWalksA(A,B,i1,j1,S,t): end: ##End ending wherever ###End Chess Pieces Procedures #ChessStory(A,B,n0): the procedure that outputs the article #about the number of walks in an A by B board, and spits out #the first n0 terms of each sequence ChessStory:=proc(a,b,n0) local t,gu,n,lu,i,gu1: if a<=4 or b<=4 then print(`a and b must be both at least 4`): RETURN(FAIL): fi: print(` In How Many Ways Can the Chess Pieces Walk n Steps, Staying on the Board? `): print(``): print(`By Shalosh B. Ekhad `): ##begin Knight print(``): gu:=KnightWalksB(a,b,1,2,t); print(`Theorem 1: Let N(n) be the number of ways a Knight can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, second column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and RETURNING TO ITS STARTING LOCATION.`): print(`We have: `): print(``): print(Sum(N(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and N(2n) is asymptotically`): print(lu): else lu:=AsyRat(gu,t,n): print(``): print(`N(n) is asymptotically`): print(lu): fi: print(``): gu:=KnightWalksA(a,b,1,2,t); print(`Theorem 1': Let N1(n) be the number of ways a Knight can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, second column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and ENDING UP ANYWHERE ON THE BOARD.`): print(`We have: `): print(``): print(Sum(N1(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): if lu<>FAIL then print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and N1(2n) is asymptotically`): print(lu): fi: else lu:=AsyRat(gu,t,n): if lu<>FAIL then print(``): print(`N1(n) is asymptotically`): print(lu): fi: fi: #####end Knight######### ##begin Bishop print(``): gu:=BishopWalksB(a,b,1,3,t); print(`Theorem 2: Let B(n) be the number of ways a Bishop can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, third column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and RETURNING TO ITS STARTING LOCATION.`): print(`We have: `): print(``): print(Sum(B(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and B(2n) is asymptotically`): print(lu): else lu:=AsyRat(gu,t,n): print(``): print(`B(n) is asymptotically`): print(lu): fi: print(``): gu:=BishopWalksA(a,b,1,3,t); print(`Theorem 2': Let B1(n) be the number of ways a Bishop can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, third column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and ENDING UP ANYWHERE ON THE BOARD.`): print(`We have: `): print(``): print(Sum(B1(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): if lu<>FAIL then print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and B1(2n) is asymptotically`): print(lu): fi: else lu:=AsyRat(gu,t,n): if lu<>FAIL then print(``): print(`B1(n) is asymptotically`): print(lu): fi: fi: #####end Bishop######### ##begin Rook print(``): gu:=RookWalksB(a,b,1,1,t); print(`Theorem 3: Let R(n) be the number of ways a Rook can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, first column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and RETURNING TO ITS STARTING LOCATION.`): print(`We have: `): print(``): print(Sum(R(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and R(2n) is asymptotically`): print(lu): else lu:=AsyRat(gu,t,n): print(``): print(`R(n) is asymptotically`): print(lu): fi: print(``): gu:=RookWalksA(a,b,1,1,t); print(`Theorem 3': Let R1(n) be the number of ways a Rook can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, first column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and ENDING UP ANYWHERE ON THE BOARD.`): print(`We have: `): print(``): print(Sum(R1(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`Comment by DZ: Even a human can get this (trivially) by pure thought! (why?)`): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): if lu<>FAIL then print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and R1(2n) is asymptotically`): print(lu): fi: else lu:=AsyRat(gu,t,n): if lu<>FAIL then print(``): print(`R1(n) is asymptotically`): print(lu): fi: fi: #####end Rook######### ##begin Queen print(``): gu:=QueenWalksB(a,b,1,4,t); print(`Theorem 4: Let Q(n) be the number of ways a Queen can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, fourth column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and RETURNING TO ITS STARTING LOCATION.`): print(`We have: `): print(``): print(Sum(Q(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and Q(2n) is asymptotically`): print(lu): else lu:=AsyRat(gu,t,n): print(``): print(`Q(n) is asymptotically`): print(lu): fi: print(``): gu:=QueenWalksA(a,b,1,4,t); print(`Theorem 4': Let Q1(n) be the number of ways a Queen can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, fourth column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and ENDING UP ANYWHERE ON THE BOARD.`): print(`We have: `): print(``): print(Sum(Q1(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): if lu<>FAIL then print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and Q1(2n) is asymptotically`): print(lu): fi: else lu:=AsyRat(gu,t,n): if lu<>FAIL then print(``): print(`Q1(n) is asymptotically`): print(lu): fi: fi: #####end Queen######### ##begin King print(``): gu:=KingWalksB(a,b,1,5,t); print(`Theorem 5: Let K(n) be the number of ways a King can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, fifth column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and RETURNING TO ITS STARTING LOCATION.`): print(`We have: `): print(``): print(Sum(K(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and K(2n) is asymptotically`): print(lu): else lu:=AsyRat(gu,t,n): print(``): print(`K(n) is asymptotically`): print(lu): fi: print(``): gu:=KingWalksA(a,b,1,5,t); print(`Theorem 5': Let K1(n) be the number of ways a King can walk`): print(` n steps on the`, a, ` by ` , b, `chessboard, starting`): print(`at its initial location, (first row, fifth column)`): print(`never getting off the board, but with no other pieces`): print(`in its way, and ENDING UP ANYWHERE ON THE BOARD.`): print(`We have: `): print(``): print(Sum(K1(n)*t^n,n=0..infinity)=gu): print(``): print(`In Maple input format it is:`): lprint(gu): print(``): print(`The first`, n0, `terms of the enumerating sequence (staring at n=1) are`): gu1:=taylor(gu,t=0,n0+1): lprint([seq(coeff(gu1,t,i),i=1..n0)]): if {seq(coeff(gu1,t,2*i-1),i=1..n0/2)}={0} then gu:=normal(subs(t=sqrt(t),gu)): lu:=AsyRat(gu,t,n): if lu<>FAIL then print(`Of course the number of ways of walking an odd number of steps`): print(`is 0, and K1(2n) is asymptotically`): print(lu): fi: else lu:=AsyRat(gu,t,n): if lu<>FAIL then print(``): print(`K1(n) is asymptotically`): print(lu): fi: fi: #####end King######### end: