A046995: Greek-key tour on 4 x n board

[hv at crypt.org]

After success with A046994, Greek-key tours on a 3 x n board, I've been
trying to crack this one too. Here's the current data:

%I A046995
%S A046995 1,4,17,52,160,469,1337,3750,10347,28249,76382,204996
%N A046995 Greek-key tours on a 4 X n board; i.e. self-avoiding walks on 4 X n grid starting in top left corner.
%D A046995 Posting by Thomas Womack (mert0236 at sable.ox.ac.uk) to sci.math newsgroup, 21 Apr 1999.
%Y A046995 Cf. A046994.
%K A046995 nonn,more,walk
%O A046995 1,2
%A A046995 xpolakis at otenet.gr (Antreas P. Hatzipolakis)

A running program today found a(25), but each successive term takes around
2.8 times longer to calculate, so the next value will take around 11 days.
The values so far found are:
1, 4, 17, 52, 160, 469, 1337, 3750, 10347, 28249, 76382, 204996, 546651,
1449952, 3828232, 10067585, 26384939, 68941126, 179658343, 467084601,
1211812016, 3138075544, 8112667259, 20941558268, 53983767498 = a(25)

Those values are enough to fill three lines for the sequence, but it'd
be nice to finish this sequence off with a formula. I feel confident that
one exists, but I'm looking for clues on how to approach searching for
a recurrence relationship - it certainly seems much more complex than
the 3 x n problem, and I haven't been able to get very far investigating
this from the definition alone.

I calculated these using a program initially written in perl (153 lines)
then translated to C (315 lines), and would be happy to make sources
for either available. I also hacked the C program to show how the a(n)
solutions were distributed around the possible endpoints, and was able
to show for example that starting at position (1,1) on a 4 x n board,
the number of solutions b(n) finishing at (4,1) is given by:
  b(0) = 0, b(1) = 1, b(2) = 1, b(3) = 4,
  b(n+4) = 2b(n+3) + 2b(n+2) - 2b(n+1) + b(n) when n >= 0
and c(n), the number of solutions finishing at (2,1), is given by:
  c(0) = 0,
  c(n+1) = c(n) + b(n) when n >= 0
.. and the fact that these sequences yielded a simple recurrence also
contributes to my belief that A046995 is tractable.

I've appended data on the breakdown of endpoints up to n=13, which
could yield some interesting sequences of its own.

I also have a more general question: for sequences like this which
are lines through a two-dimensional number space, how many entries
in the EIS database are justified? I also have data for a 5 x n
board up to n=14 and a 6 x n board up to n=11, and could calculate
a few more terms if they would be of interest. Similar sequences
I've been considering are for king's move tours (ie diagonal moves
also allowed) including or excluding self-crossing walks.

Hugo van der Sanden
---
'*' marks the starting point; entries are the number of tours that
finish at that endpoint. A046995(n) is the sum of entries for the
given 4 x n board.
4 x 1: 1
  1 
  0
  0
  *
4 x 2: 4
  1 0  
  0 1
  1 0
  * 1
4 x 3: 17
  4 0 4 
  0 4 0
  2 0 1
  * 2 0
4 x 4: 52
  8 0 4 0 
  0 8 0 4
  6 0 8 0
  * 6 0 8
4 x 5: 160
  23  0 15  0 20 
   0 23  0 20  0
  14  0 14  0  8
   * 14  0  9  0
4 x 6: 469
  55  0 33  0 23  0
   0 55  0 39  0 20
  37  0 43  0 47  0
   * 37  0 33  0 47
4 x 7: 1337
  144   0  90   0  82   0 111
    0 144   0 114   0 111   0
   92   0  99   0  87   0  47
    *  92   0  72   0  52   0
4 x 8: 3750
  360   0 220   0 182   0 126   0
    0 360   0 270   0 210   0 111
  236   0 264   0 260   0 264   0
    * 236   0 197   0 190   0 264
4 x 9: 10347
  921   0 569   0 494   0 454   0 624
    0 921   0 710   0 622   0 624   0
  596   0 654   0 608   0 496   0 264
    * 596   0 481   0 417   0 296   0
4 x 10: 28249
  2329    0 1431    0 1211    0 1002    0  703    0
     0 2329    0 1771    0 1462    0 1174    0  624
  1517    0 1681    0 1609    0 1473    0 1480    0
     * 1517    0 1245    0 1138    0 1073    0 1480
4 x 11: 76382
  5924    0 3650    0 3128    0 2727    0 2543    0 3505
     0 5924    0 4536    0 3859    0 3485    0 3505    0
  3846    0 4241    0 4001    0 3457    0 2785    0 1480
     * 3846    0 3130    0 2782    0 2363    0 1665    0
4 x 12: 204996
  15024     0  9244     0  7872     0  6676     0  5604     0  3944     0
      0 15024     0 11464     0  9608     0  8181     0  6593     0  3505
   9770     0 10800     0 10264     0  9132     0  8266     0  8305     0
      *  9770     0  7985     0  7196     0  6438     0  6026     0  8305
4 x 13: 546651
  38159     0 23495     0 20072     0 17256     0 15263     0 14274     0 19676
      0 38159     0 29168     0 24632     0 21608     0 19572     0 19676     0
  24794     0 27374     0 25920     0 22728     0 19406     0 15626     0  8305
      * 24794     0 20221     0 18097     0 15752     0 13278     0  9346     0