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

1, 5, 38, 160, 824, 3501, 16262, 68591, 304177, 1276805, 5522791, 23117164, 98562435, 411870513, 1740941765, 7267608829, 30557297042, 127482101761, 534250130959, 2227966210989, 9317736040747, 38847892461656, 162258421050635, 676389635980185, 2822813259030961, 11766012342819549

Offset: 1

Author

Nathaniel Johnston, Oct 03 2008

Keywords

• nonn

Comments

From Andrew Howroyd, Nov 07 2015: (Start)

Greek Key Tours are self-avoiding walks that touch every vertex of the grid and start at the top-left corner.

The sequence may be enumerated using standard methods for counting Hamiltonian cycles on a modified graph with two additional nodes, one joined to a corner vertex and the other joined to all other vertices.

(End)

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Nathaniel Johnston, Self-avoiding walks table of values
• 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 p. 30.
• Index entries for linear recurrences with constant coefficients, signature (4,14,-54,-33,117,2,-84,-6,9,0,-14,0,-2).

Crossrefs

Row 5 of A378938.

Cf. A046994, A046995, A145157.

Formula

G.f.: -x*(3*x^13 -3*x^12 +17*x^11 -11*x^10 +11*x^9 -21*x^8 +67*x^7 -29*x^6 -65*x^5 +45*x^4 +8*x^3 -4*x^2 -x -1) / ((x +1)*(x^6 -x^5 +8*x^4 -8*x^3 -2*x^2 +5*x -1)*(2*x^6 +11*x^2 -1)). [conjectured by Colin Barker, Nov 09 2015; proved by Jay Pantone, Klotz, and Sullivan, Aug 01 2024]

Extensions

a(11)-a(15) added by Nathaniel Johnston, Oct 12 2008

a(16) added by Ruben Zilibowitz, Jul 10 2015

a(17) onwards from Andrew Howroyd, Nov 07 2015