> # To start the program
> restart:
># Finding all the binary vectors of length k.
For example, vecbin(3) return all
the binary vectors of length 3.
>vecbin:=proc() local
k,i,j,ii,vec,a:
k:=args[1]: vec:=linalg[vector](2^k,[]):
a:=linalg[vector](k,[]);
for i from 1 to k do a[i]:=0: vec[1]:=convert(a,list):
od:
for i from 2 to 2^k do
for
j from k by -1 while a[j]=1 do od:
a[j]:=1:
for ii from j+1 to k do a[ii]:=0: od:
vec[i]:=convert(a,list):
od:
RETURN(convert(vec,list)):
end:
># Checking if the vectors a and b are cross-orthogonal
(see the definition in the paper)
>fedge:=proc() local
k,a,b,i:
k:=args[1]: a:=args[2]: b:=args[3]:
for i from 1 to k-1 do if a[i]*b[i+1]=1 then RETURN(0)
fi: od:
for i from 1 to k-1 do if a[i+1]*b[i]=1 then RETURN(0)
fi: od:
RETURN(1):
end:
># Checking if the vectors a and b are consecutive
columns in the matrix L_{m,n}.
>pkedge:=proc() local
k,a,b,i: k:=args[1]: a:=args[2]: b:=args[3]:
for i from 1 to k-1 do if a[i]*b[i+1]=1 then RETURN(0)
fi: od:
for i from 1 to k-1 do if a[i+1]*b[i]=1 then RETURN(0)
fi: od:
for i from 1 to k do if a[i]*b[i]=1 then RETURN(0)
fi: od:
for i from 1 to k-1 do if a[i]*a[i+1]=1 then RETURN(0)
fi: od:
for i from 1 to k-1 do if b[i]*b[i+1]=1 then RETURN(0)
fi: od:
RETURN(1):
end:
>#Finding the transfer matrix T_m (see the paper) .
>pawns:=proc() local
k,vec,T,i,j:
m:=args[1]: vec:=vecbin(m): T:=linalg[matrix](2^m,2^m,[]):
for i from 1 to 2^m do
for j from 1 to 2^m do
if fedge(m,vec[i],vec[j])=1
then T[i,j]:=1: else T[i,j]:=0: fi:
od:
od:
print("The trnasfer-matrix for the problem of
pawns on ",m,"rows is given by");
RETURN(convert(T,matrix));
end:
>#Finding the transfer matrix A_m (for the matrices
L_{m,n}, see the paper) .
>pawns_kings:=proc()
local m,vec,A,i,j:
m:=args[1]: vec:=vecbin(m): A:=linalg[matrix](2^m,2^m,[]):
for i from 1 to 2^m do
for j from 1 to 2^m do
if pkedge(m,vec[i],vec[j])=1
then A[i,j]:=1: else A[i,j]:=0: fi:
od:
od:
print("The matrix for the pawns-king of",m,"rows
is given by");
RETURN(convert(A,matrix));
end:
>#Now let us present some examples.
>T:=pawns(2);
T:= matrix([[1, 1, 1, 1], [1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 0]])
> #The sequence M_{2,n} is given
by (find evalm(T^n&*[1,1,...,1])[1] for n=0,1,2,...,20:
1, 4, 9, 25, 64, 169, 441, 1156, 3025,
7921, 20736, 54289, 142129, 372100, 974169, 2550409, 6677056, 17480761,
45765225, 119814916, 313679521
>A:=pawns_kings(2);
A := matrix([[1, 1, 1, 0], [1, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0]])
> #The sequence L_{2,n} is given
by (find evalm(A^n&*[1,1,...,1])[1] for n=0,1,2,...,20:
1, 3, 5, 11, 21,
43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763,
349525, 699051, 1398101
>T:=pawns(3);
T := matrix([[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 1, 1, 0, 0], [1, 0,
1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 1,
0, 0],
[1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0]])
> #The sequence M_{3,n} is
given by
1, 8, 25, 119, 484, 2117, 9025,
38936, 167281, 720083, 3097600, 13329209, 57350329, 246768392, 1061782225,
4568619071, 19657722436, 84582794333, 363940725625, 1565955363224, 6737954403049
>A:=pawns_kings(3);
A := matrix([[1, 1, 1, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 0, 0, 0], [1, 0,
0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0,
0, 0],
[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]])
> #The sequence L_{3,n} is given
by
1, 5, 11, 35, 93, 269, 747,
2115, 5933, 16717, 47003, 132291, 372157, 1047181, 2946251, 8289731, 23323853,
65624397, 184640891, 519507267, 1461688413
>T:=pawns(4);
T := matrix([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0,
0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0]])
> #The sequence M_{4,n} is given
by
1, 16, 64, 484, 2704, 17424, 104976,
652864, 4000000, 24681024, 151782400, 934891776, 5754132736, 35428274176,
218096472064, 1342706197504, 8266039005184, 50888705511424, 313286601609216,
1928696564957184, 11873676328960000
>A:=pawns_kings(4);
A := matrix([[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0], [1, 0, 0,
0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0]])
> #The sequence L_{4,n} is given
by
1, 8, 21, 93, 314, 1213, 4375, 16334,
59925, 221799, 817280, 3018301, 11134189, 41096528, 151643937, 559640289,
2065192514, 7621289593, 28124714395, 103789150046, 383013144129
> #The sequence M_{5,n} is given by
1, 32, 169, 2117, 17424, 177073, 1630729,
15786848, 149352841, 1429585373, 13610488896, 129934154497, 1238878076401,
11819811992192, 112736763711049, 1075437390934037, 10258292274099984, 97854335246290033,
933422273708422969, 8903889548092007168, 84933643514825414761
> #The sequence L_{5,n} is given by
1, 13, 43, 269, 1213, 6427, 31387, 159651,
795611, 4005785, 20064827, 100764343, 505375405, 2536323145, 12724855013,
63851706457, 320373303983, 1607526474153, 8065864257905, 40471399479495,
203068825478591
> #The sequence M_{6,n} is given by
1, 64, 441, 9025, 104976, 1630729,
21836929, 315701824, 4388400025, 62249751001, 873880953856, 12333757683025,
173597094140625, 2446840043215936, 34462915406893801, 485580777431805169,
6840488501157755536, 96373115267172331225
> #The sequence L_{6,n} is given by
1, 21, 85, 747, 4375, 31387,
202841, 1382259, 9167119, 61643709, 411595537, 2758179839, 18448963469,
123518353059, 826573277157, 5532716266089, 37028886137273, 247839719105625,
1658772577825883, 11102227136885119, 74306982478800839
# To find the formula for the number M_{m,n} (or L_{m,n}),
for example M_{3,n}, we use the package
linalg, as with(linalg);,
find the nonzero eigenvalues of T_m (or
A_m), aseigenvalues(T) (or eigenvalues(A)); say a_1,a_2,...,a_s,
and finally we solve the equations
b_1 a_1^j + b_2 a_2^j + ... + b_s a_s^j=c_j where j=0,1,...,s-1
such that c_j is given by the Maple command:
evalm(T^j&*[1,1,....,1])[1] (or evalm(A^j&*[1,1,...,1])[1]
)
(where [1,1,...,1] occurs 1's exactly
2^m).