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,2

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

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]

Crossrefs

Row 4 of A378938.

Cf. A046994.

Sequence in context: A047668 A208658 A092091 * A001585 A060262 A157492

Adjacent sequences: A046992 A046993 A046994 * A046996 A046997 A046998

Keyword

nonn,easy,walk

Author

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

Extensions

More terms from Hugo van der Sanden, Apr 02 2003

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

Status

approved