A046994 -id:A046994 - 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

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 8, 4, 1, 1, 5, 17, 17, 5, 1, 1, 6, 38, 52, 38, 6, 1, 1, 7, 78, 160, 160, 78, 7, 1, 1, 8, 164, 469, 824, 469, 164, 8, 1, 1, 9, 332, 1337, 3501, 3501, 1337, 332, 9, 1, 1, 10, 680, 3750, 16262, 22144, 16262, 3750, 680, 10, 1

Offset: 1

Andrew Howroyd, Dec 20 2024

These paths are also called Greek-key tours. The path can end anywhere.

			Array begins:
======================================================
m\n | 1 2   3    4     5      6        7         8 ...
----+-------------------------------------------------
  1 | 1 1   1    1     1      1        1         1 ...
  2 | 1 2   3    4     5      6        7         8 ...
  3 | 1 3   8   17    38     78      164       332 ...
  4 | 1 4  17   52   160    469     1337      3750 ...
  5 | 1 5  38  160   824   3501    16262     68591 ...
  6 | 1 6  78  469  3501  22144   144476    899432 ...
  7 | 1 7 164 1337 16262 144476  1510446  13506023 ...
  8 | 1 8 332 3750 68591 899432 13506023 180160012 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)

Main diagonal is A145157.
Rows 1..8 are A000012, A000027, A046994, A046995, A145156, A160240, A160241, A374307.
Cf. A332307, A064298, A271465, A271592, A288518.

T(m,n) = T(n,m).

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

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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