The problem of the Pawns
This program find the transfer-matrix (T_m) for the sequence M_{m,n} in the paper:
                             The problem of the pawns
                                      authored by
                    Toufik Mansour and Sergey Kitaev.
Also, the program find the sequence L_{m,n} by find the transfer-matrix A_m for the number of mxn binary matrices with no 1's in any row, column, and diagonal. For example, L_{2,2}=5, namely the matrices [[0,0],[0,0]] , [[1,0],[0,0]] , [[0,1],[0,0]], [[0,0],[1,0]] , and  [[0,0],[0,1]].

> # 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).



Update on 20 May 2003.