[seqfan] Re: Rook walk generates A081057?

Richard Mathar mathar at strw.leidenuniv.nl
Wed Sep 29 20:00:02 CEST 2010

```Futher on http://list.seqfan.eu/pipermail/seqfan/2010-September/006106.html :

On the 3x3 board the walks are
1,2,6,16,48,128,384,1024,3072,8192,24576,65536,196608,524288,1572864,4194304,
12582912,33554432,100663296,268435456,805306368
apparently a(n)= +8*a(n-2) = 2*A096886(n-1).

On the 4x4 board the walks are
1,2,6,18,58,186,602,1946,6298,20378,65946,213402,690586,2234778,7231898,23402906,
75733402,245078426,793090458,2566494618,8305351066
(as claimed and hereby confirmed).
apparently a(n)= +3*a(n-1) +2*a(n-2) -4*a(n-3) = A081057(n),

On the 5x5 board the walks are
1,2,6,18,60,198,684,2322,8100,27702,96876,331938,1161540,
3981798,13935564,47777202,167218020,573313302,2006589996,6879720258,24079001220
apparently a(n)= +15*a(n-2) -36*a(n-4),

On the 6x6 board the walks are
1,2,6,18,60,200,698,2432,8658,30762,110374,395428,1422916,5115398,18426284,
66337562,239038938,861091106,3103170820,11181360464,40296216194
apparently a(n)= +4*a(n-1) +5*a(n-2) -27*a(n-3) +10*a(n-4) +16*a(n-5) -8*a(n-6)

By Maple:

# The side length of the board
rsid := 6 ;
# compute the rsid by rsid matrix of number of ways of reaching the
# individual positions from a previous matrix 'prevm'
wal := proc(prevm)
global rsid ;
a := array(1..rsid,1..rsid) ;
# could have reached the 4 corners by 2 previous positions each
a[1,1] := prevm[1,2]+prevm[2,1] ;
a[1,rsid] := prevm[1,rsid-1]+prevm[2,rsid] ;
a[rsid,1] := prevm[rsid-1,1]+prevm[rsid,2] ;
a[rsid,rsid] := prevm[rsid,rsid-1]+prevm[rsid-1,rsid] ;
# could have reached any position not on the edges/corners
# from 4 different adjacnet positions
for r from 2 to rsid-1 do
for c from 2 to rsid-1 do
a[r,c] := prevm[r-1,c]+prevm[r+1,c]+prevm[r,c+1]+prevm[r,c-1] ;
end do:
end do:
# could have reached the top or bottom edges from 3 different positions
for c from 2 to rsid-1 do
a[1,c] := prevm[2,c]+prevm[1,c+1]+prevm[1,c-1] ;
a[rsid,c] := prevm[rsid-1,c]+prevm[rsid,c+1]+prevm[rsid,c-1] ;
end do:
# could have reached the left or right edges from 3 different positions
for r from 2 to rsid-1 do
a[r,1] := prevm[r,2]+prevm[r-1,1]+prevm[r+1,1] ;
a[r,rsid] := prevm[r,rsid-1]+prevm[r-1,rsid]+prevm[r+1,rsid] ;
end do:
return a;
end proc:

# starting position has only a single [1,1] element occupied, the others zero
rw := array(1..rsid,1..rsid) ;
for r from 1 to rsid do
for c from 1 to rsid do
rw[r,c] := 0 ;
end do;
end do;
rw[1,1] := 1 ;
# walk t times by updating the matrix
for t from 1 to 20 do
rw := wal(rw) ;
an := 0 ;
for r from 1 to rsid do
for c from 1 to rsid do
an := an+rw[r,c] ;
end do:
end do:
# report total number of walks, the sum over all the matrix entries
printf("%d,",an) ;
end do:

```