[seqfan] Re: Rook walk generates A081057?

[Richard Mathar]

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

The could perhaps be approached by verifying the recurrence
a(n)= 3*a(n-1) + 2*a(n-2)-4*a(n-3). The walk has a certain markovian property,
the number of ways of moving away from one of the 4 corner positions is 2,
away from one of the 8 remaing side positions is 3, and away from one of
the 4 middle positions is 4.
  On the average, in the vague sense of representing the majority, the number
of next positions is 3 which could correspond to the factor 3
in front of a(n-1). The error in the statistics is then corrected by
looking at the 8 positions (4 center and 4 corners) counted incorrectly.
Adding 2*a(n-2)>0 would be related to the probability of being in the center,
where +1*a(n-1) is the site-correction, adding -4*a(n-3) would be related to the
probability of being in one of the corners, where  -a(n-1) is the site
correction.
  This sort of interpretation is tedious because a(n-2) counts the numbers
of ways of having been at some other or the same site previously, multiply
correlated with the various hook-lenghts. The only sober way  of counting
these is to look at the full 16-site probability matrix (perhaps a 4-site
representation with one of the subsquares will do by symmetry) and to compute
the transitions matrix (number op hops), where its eigenvalues should become
one of those of the characteristic equation of A081057 if the connection
is indeed as observed:

  a11 = 0 *a11 + 1* a12 + 0 *a13+0*a14+...+1*a21+0*a22+...
           (so square a11 is reached either from a12 or a21 but from nowhere else)
  a12 = 1*a11+ 0*a12 + 1*a13 +0*a14+0*a21+1*a22++0*a32+...
  a13 = 
  a14 = 
  a21 = 
  ..
  a44 = 
a(n) =sum aij with starting vector (1,0,0,0,0,...0).
Obviously I am too lazy to write this down myself :-). Perhaps a related
check is to consider the walks on a 3x3 board first or on a 5x5 board,
which are also expected to generate linear recurrences.

RJM