A046995 Number of Greek-key tours on a 4 X n board; i.e., self-avoiding walks on 4 X n grid starting in top left corner.

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, 138989629481, 357450757247, 918350963486, 2357213935865, 6045360575469

Offset: 1

Author

Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr)

Keywords

• nonn
• easy
• walk

References

• Posting by Thomas Womack (mert0236(AT)sable.ox.ac.uk) to sci.math newsgroup, Apr 21 1999.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Jay Pantone, Alexander R. Klotz, and Everett Sullivan, Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height, arXiv:2407.18205 [math.CO], 2024. See pp. 26, 30.
• Index entries for linear recurrences with constant coefficients, signature (3,3,-9,-6,5,1,-3,1).

Crossrefs

Row 4 of A378938.

Cf. A046994.

Formula

a(n) = 3a(n-1)+3a(n-2)-9a(n-3)-6a(n-4)+5a(n-5)+a(n-6)-3a(n-7)+a(n-8) for n>=10. [conjectured by Dean Hickerson, Apr 05 2003; proved by Jay Pantone, Klotz, and Sullivan, Aug 01 2024]

G.f.: x*(-(x-1)*(x^7-x^6-2*x^5+3*x^4-2*x^3-4*x^2-2*x-1))/((x^4-2*x^3+2*x^2+2*x-1)*(x^4-x^3-3*x^2-x+1)). [conjectured by Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009; proved by Jay Pantone, Klotz, and Sullivan, Aug 01 2024]

Extensions

More terms from Hugo van der Sanden, Apr 02 2003

a(26) onwards from Andrew Howroyd, Dec 21 2024