A378938 -id:A378938 - cp's OEIS frontend

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

1, 2, 8, 52, 824, 22144, 1510446, 180160012, 54986690944, 29805993260994, 41433610713353366, 103271401574007978038, 660340630211753942588170, 7618229614763015717175450784, 225419381425094248494363948728158

Offset: 1

Nathaniel Johnston, Oct 03 2008

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. - Andrew Howroyd, Nov 08 2015

Nathaniel Johnston, On Maximal Self-Avoiding Walks
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

Main diagonal of A378938.
Cf. A046994, A046995, A145156, A160240, A160241.
Cf. A000532, A001184, A120443, A003763, A271507, A007764.

a(9)-a(15) from Andrew Howroyd, Nov 08 2015

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.

Original entry on oeis.org

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

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

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

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

Row 4 of A378938.

Cf. A046994.

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]

More terms from Hugo van der Sanden, Apr 02 2003

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

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

Original entry on oeis.org

1, 3, 8, 17, 38, 78, 164, 332, 680, 1368, 2768, 5552, 11168, 22368, 44864, 89792, 179840, 359808, 720128, 1440512, 2882048, 5764608, 11531264, 23063552, 46131200, 92264448, 184537088, 369078272, 738172928, 1476354048, 2952740864, 5905498112, 11811061760, 23622156288

Offset: 1

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

			On a 3 X 3 board labeled 123 456 789 (reading across rows), 125478963 is such a tour.

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

Robert Israel, Table of n, a(n) for n = 1..2985
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.
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Row 3 of A378938.

Cf. A046995.

A046994:=n->`if`(n=1,1,11*2^(n-3)-(4+(-1)^n)*(2^((1/4)*(2*n-7-(-1)^n)))): seq(A046994(n), n=1..30); # Wesley Ivan Hurt, Sep 14 2014

CoefficientList[Series[(1 + x - x^3)/(1 - 2 x - 2 x^2 + 4 x^3), {x, 0, 30}], x] (* Wesley Ivan Hurt, Sep 14 2014 *)

a(1) = 1; a(2m) = Sum_{i = 2...2m-1} a(i) + 3*2^(m-1); a(2m+1) = Sum_{i = 2...2m} a(i) + 5*2^(m-1).
a(n) = 11*2^(n-3) - (4 + (-1)^n)*(2^((1/4)*(2n - 7 - (-1)^n))), n >= 2. - Nathaniel Johnston, Feb 03 2006
a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3) for n>4. G.f.: x*(1+x-x^3)/(1-2*x-2*x^2+4*x^3). - Colin Barker, Jul 19 2012

More terms and formula from Hugo van der Sanden

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.

Original entry on oeis.org

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

Nathaniel Johnston, Oct 03 2008

nonn

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)

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

Row 5 of A378938.

Cf. A046994, A046995, A145157.

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]

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

A160240 Number of Greek-key tours on a 6 X n grid.

Original entry on oeis.org

1, 6, 78, 469, 3501, 22144, 144476, 899432, 5585508, 34092855, 206571444, 1241016042, 7407467656, 43975776229, 259779839242, 1528563721468, 8960651209082, 52368047294410, 305173796833144, 1774059940879290, 10289839706255591, 59564855651625602, 344177608427972004, 1985502681113986836

Offset: 1

Nathaniel Johnston, May 05 2009

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-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. - Andrew Howroyd, Nov 07 2015

Andrew Howroyd, Table of n, a(n) for n = 1..500
Nathaniel Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
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, order 37.

Row 6 of A378938.

Cf. A046994, A046995, A145156, A145157.

See Links section for generating function. - Jay Pantone, Aug 01 2024

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

A160241 Number of Greek-key tours on a 7 X n grid.

Original entry on oeis.org

1, 7, 164, 1337, 16262, 144476, 1510446, 13506023, 132712481, 1185979605, 11264671456, 100572103736, 935551716239, 8347069749600, 76604373779441, 683160282998544, 6213169249692192, 55392188422262591, 500676083630457127, 4462726297606450762, 40165465812088131228, 357958181000067374304

Offset: 1

Nathaniel Johnston, May 05 2009

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-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. - Andrew Howroyd, Nov 07 2015

Andrew Howroyd, Table of n, a(n) for n = 1..500
Nathaniel Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
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. 31.
Index entries for linear recurrences with constant coefficients, order 71.

Row 7 of A378938.

Cf. A046994, A046995, A145156, A145157.

See Links section for generating function. Jay Pantone, Aug 06 2024

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

A374307 Number of Greek-key tours on an 8 X n grid.

Original entry on oeis.org

1, 8, 332, 3750, 68591, 899432, 13506023, 180160012, 2510785227, 33330848454, 448079715759, 5893418278271, 77649390052196, 1011970457365017, 13165754032331389, 170232985496817728, 2195480228590892060, 28203099820000893198, 361391865363036263917, 4617813892310295762334

Offset: 1

Jay Pantone, Jul 23 2024

nonn

Greek-key tours are self-avoiding walks that touch every vertex of the grid and start at the bottom-left corner.

Andrew Howroyd, Table of n, a(n) for n = 1..200
N. Johnston, On Maximal Self-Avoiding Walks.
Jay Pantone, Generating function.
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.
Index entries for linear recurrences with constant coefficients, order 203.

Row 8 of A378938.

Cf. A145157, A046994, A046995, A145156, A160240, A160241.

See Links section for generating function.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A160240 Number of Greek-key tours on a 6 X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A160241 Number of Greek-key tours on a 7 X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A374307 Number of Greek-key tours on an 8 X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions