A271592 -id:A271592 - cp's OEIS frontend

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

1, 1, 2, 8, 86, 1770, 88418, 8934966, 2087813834, 1013346943033, 1111598871478668, 2568944901392936854, 13251059359839620127088, 145194816279817259193401518, 3524171261632305641165676374930, 182653259988707123426135593460533473

Offset: 1

Russ Cox, Mar 15 1996

Number of walks reaching each cell exactly once.

Oliver R. Bellwood, Table of n, a(n) for n = 1..20 (first 19 terms from KeyTo9(AT)Fans, Ed Wynn)
KeyTo9(AT)Fans, Counting paths in a grid - Chinese web page giving the sequence up to 18 items.
Douglas M. McKenna, Tendril Motifs for Space-Filling, Half-Domino Curves, in: Bridges Finland Conference Proceedings, 2016, pp. 119-126.
Douglas M. McKenna, Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing Medium?, Bridges Conf. Proc.; Math., Art, Music, Architecture, Culture (2023) 91-98.

Main diagonal of A271592.
Cf. A181688, A181689, A014524, A014585.
Cf. A001184, A145157, A120443, A003763, A271507, A007764, A121785, A121789.
See also A350148.

More terms from Zhao Hui Du, Jul 08 2008
Edited by Franklin T. Adams-Watters, Jul 03 2009
Name clarified by Andrew Howroyd, Apr 10 2016

A332307 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n grid graph.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 14, 20, 14, 1, 1, 22, 62, 62, 22, 1, 1, 32, 132, 276, 132, 32, 1, 1, 44, 336, 1006, 1006, 336, 44, 1, 1, 58, 688, 3610, 4324, 3610, 688, 58, 1, 1, 74, 1578, 12010, 26996, 26996, 12010, 1578, 74, 1, 1, 92, 3190, 38984, 109722, 229348, 109722, 38984, 3190, 92, 1

Offset: 1

Andrew Howroyd, Feb 09 2020

			Array begins:
================================================
m\n | 1  2   3     4      5       6        7
----+-------------------------------------------
  1 | 1  1   1     1      1       1        1 ...
  2 | 1  4   8    14     22      32       44 ...
  3 | 1  8  20    62    132     336      688 ...
  4 | 1 14  62   276   1006    3610    12010 ...
  5 | 1 22 132  1006   4324   26996   109722 ...
  6 | 1 32 336  3610  26996  229348  1620034 ...
  7 | 1 44 688 12010 109722 1620034 13535280 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path

Rows n=1..9 are A000012, A003682, A003685, A003695, A003778, A145402, A358794, A358795, A358796.
Main diagonal is A120443.
Cf. A064298, A231829, A271465, A271592, A288518, A321172.

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

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 3, 12, 3, 6, 49, 49, 6, 10, 146, 322, 146, 10, 15, 373, 1618, 1618, 373, 15, 21, 872, 7119, 14248, 7119, 872, 21, 28, 1929, 28917, 111030, 111030, 28917, 1929, 28, 36, 4118, 111360, 801756, 1530196, 801756, 111360, 4118, 36

Offset: 1

Andrew Howroyd, Jun 10 2017

Paths of length zero are not counted here.

			Table starts:
=================================================================
m\n|  1    2      3       4         5          6            7
---|-------------------------------------------------------------
1  |  0    1      3       6        10         15           21 ...
2  |  1   12     49     146       373        872         1929 ...
3  |  3   49    322    1618      7119      28917       111360 ...
4  |  6  146   1618   14248    111030     801756      5493524 ...
5  | 10  373   7119  111030   1530196   19506257    235936139 ...
6  | 15  872  28917  801756  19506257  436619868   9260866349 ...
7  | 21 1929 111360 5493524 235936139 9260866349 343715004510 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Rows 2-7 are A288516, A288527, A358800, A358801, A358802, A358803.
Main diagonal is A288032.
Cf. A231829, A064298, A271465, A271592, A120443, A001184, A145157, A003763.

A333580 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in an n X k grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 4, 4, 1, 1, 1, 0, 8, 0, 8, 0, 1, 1, 1, 16, 20, 20, 16, 1, 1, 1, 0, 32, 0, 104, 0, 32, 0, 1, 1, 1, 64, 111, 378, 378, 111, 64, 1, 1, 1, 0, 128, 0, 1670, 0, 1670, 0, 128, 0, 1, 1, 1, 256, 624, 6706, 10204, 10204, 6706, 624, 256, 1, 1

Offset: 1

Seiichi Manyama, Mar 27 2020

			Square array T(n,k) begins:
  1, 1,  1,   1,    1,     1,      1,      1, ...
  1, 0,  1,   0,    1,     0,      1,      0, ...
  1, 1,  2,   4,    8,    16,     32,     64, ...
  1, 0,  4,   0,   20,     0,    111,      0, ...
  1, 1,  8,  20,  104,   378,   1670,   6706, ...
  1, 0, 16,   0,  378,     0,  10204,      0, ...
  1, 1, 32, 111, 1670, 10204, 111712, 851073, ...
  1, 0, 64,   0, 6706,     0, 851073,      0, ...

Andrew Howroyd, Table of n, a(n) for n = 1..378
Index entries for sequences related to graphs, Hamiltonian

Rows n=1..10 (with 0 omitted) give: A000012, A000035, A011782(n-1), A014523, A014584, A333581, A333582, A333583, A333584, A333585.
T(2*n-1,2*n-1) gives A001184(n-1).
Cf. A271592.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333580(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A333580(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])

T(n,k) = T(k,n).

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

A014585 Number of Hamiltonian paths in a 5 X n grid starting in the lower left corner and ending in the lower right.

Original entry on oeis.org

0, 0, 1, 4, 23, 86, 397, 1584, 6820, 28002, 117852, 488824, 2043133, 8502298, 35463855, 147729456, 615817511, 2566065066, 10694840588, 44568760860, 185743671308, 774073998864, 3225960662493, 13444082934608

Offset: 0

N. J. A. Sloane

nonn

The difference between A014584 and A014585 needs to be clarified. - N. J. A. Sloane, Feb 08 2013

The difference is that A014584 counts paths starting in the LL finishing in the UR. A014585 counts paths starting in the LL finishing the LR. - Ruben Zilibowitz, Jul 05 2015

K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.
Index entries for sequences related to graphs, Hamiltonian

Column 5 of A271592.

Cf. A000532, A181689, A014584, A014524, A003778, A006865.

The reference gives a generating function.

Definition clarified by Ruben Zilibowitz, Jul 05 2015

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Original entry on oeis.org

1, 1, 4, 8, 23, 55, 144, 360, 921, 2329, 5924, 15024, 38159, 96847, 245888, 624176, 1584593, 4022609, 10211940, 25924088, 65811431, 167069767, 424126160, 1076693080, 2733310377, 6938824361, 17615009476, 44717740000, 113521160607, 288186606623

Offset: 1

Sean A. Irvine, Nov 17 2010

			Illustration of a(1)=a(2)=1:
   .    .__.
   |    .__|
   |    |__
   |    .__|
Illustration of a(3)=4:
   .__.__.    .  .__.    .  .__.    .__.__.
   .__.__|    |__|  |    |  |  |    .__.  |
   |__.__.    .__.  |    |__|  |    |  |  |
   .__.__|    |  |__|    .__.__|    |  |__|

Index entries for linear recurrences with constant coefficients, signature (2, 2, -2, 1).

Row 4 of A271592.

Cf. A000532, A014524, A014523, A181689, A003695, A006864.

LinearRecurrence[{2, 2, -2, 1}, {1, 1, 4, 8}, 30] (* T. D. Noe, Nov 06 2013 *)

G.f.: (x^2-x)/(x^4-2*x^3+2*x^2+2*x-1).

a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4), n > 4.

G.f. formula reverted to the original (correct) value by Stefan Bühler, Nov 06 2013

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Original entry on oeis.org

0, 1, 8, 47, 264, 1480, 8305, 46616, 261663, 1468752, 8244304, 46276385, 259755560, 1458042831, 8184190168, 45938958232, 257861540369, 1447411446840, 8124514782015, 45603992276896, 255981331487648

Offset: 0

N. J. A. Sloane

			Illustration of a(1)=1:
   .__.__.__.
   .__.__.__|
Illustration of a few of the 8 solutions to a(2):
   .__.__.__.    .  .__.__.    .  .__.__.    .__.__.__.
   .__.__.  |    |  |  .__|    |__|  .__|    .__.__.__|
   |__   |  |    |__|  |__.    .__.  |__.    |__.__.__.
   .__|  |__|    .__.__.__|    |  |__.__|    .__.__.__|

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.
Index entries for sequences related to graphs, Hamiltonian
Index entries for linear recurrences with constant coefficients, signature (7,-9,7,-1).

Even bisection of column 4 of A271592.

Cf. A000532, A181688, A014523, A014585, A003695, A006864.

CoefficientList[Series[x (x + 1)/(x^4 - 7 x^3 + 9 x^2 - 7 x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Oct 15 2013 *)

From Colin Barker, May 20 2013: (Start)
a(n) = 7*a(n-1)-9*a(n-2)+7*a(n-3)-a(n-4).
G.f.: x*(x+1)/(x^4-7*x^3+9*x^2-7*x+1). (End)

Name clarified by Andrew Howroyd, Apr 10 2016

A181689 Number of maximal self-avoiding walks from NW to SW corners of a 5 X n grid.

Original entry on oeis.org

1, 0, 8, 0, 86, 0, 948, 0, 10444, 0, 115056, 0, 1267512, 0, 13963520, 0, 153828832, 0, 1694652176, 0, 18669100976, 0, 205667768400, 0, 2265734756752, 0, 24960420526224, 0, 274975961325264, 0, 3029267044091408, 0, 33371858326057936, 0, 367640393509287824, 0, 4050102862690348880, 0, 44617875206245953552, 0, 491531908055724064720, 0, 5414951194338345409680, 0, 59653698888134291413584, 0, 657173751585588653678864, 0, 7239741169830151881286864

Offset: 1

Sean A. Irvine, Nov 17 2010

All even terms are 0.

Index entries for linear recurrences with constant coefficients, signature (0,11,0,0,0,2).

Row 5 of A271592.

Cf. A000532, A003778, A006865, A014584, A014585, A181688.

I:=[1,0,8,0,86,0]; [n le 6 select I[n] else 11*Self(n-2)+2*Self(n-6): n in [1..50]]; // Wesley Ivan Hurt, Apr 10 2016

A181689:=proc(n) option remember:
if n mod 2 = 0 then 0 elif n=1 then 1 elif n=3 then 8 elif n=5 then 86 else 11*a(n-2)+2*a(n-6); fi; end: seq(A181689(n), n=1..50); # Wesley Ivan Hurt, Apr 10 2016

CoefficientList[Series[(1 - 3*x^2 - 2*x^4)/(1 - 11*x^2 - 2*x^6), {x, 0, 50}], x] (* Wesley Ivan Hurt, Apr 10 2016 *)

x='x+O('x^99); Vec(x*(1-3*x^2-2*x^4)/(1-11*x^2-2*x^6)) \\ Altug Alkan, Apr 11 2016

G.f.: x*(1 - 3*x^2 - 2*x^4)/(1 - 11*x^2 - 2*x^6).

a(n) = 11*a(n-2) + 2*a(n-6) for n>6. - Wesley Ivan Hurt, Apr 10 2016

A333604 Number of directed Hamiltonian walks from NW to SW corners of an 8 X n grid.

Original entry on oeis.org

1, 1, 64, 264, 6820, 52387, 909009, 8934966, 130373192, 1440623260, 19338414411, 226336038320, 2916455246831, 35119270968805, 443497762883269, 5416278334971240, 67721300861621626, 832844111255909543, 10362230473284966919

Offset: 1

Seiichi Manyama, Mar 28 2020

nonn

Ed Wynn, Table of n, a(n) for n = 1..89

Row n=8 of A271592.

Cf. A333583.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A271592(n, k):
    if k == 1: return 1
    universe = tl.grid(k - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def A333604(n):
    return A271592(8, n)
print([A333604(n) for n in range(1, 9)])

More terms from Ed Wynn, Jun 25 2023

cp's OEIS Frontend

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A332307 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A333580 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of Hamiltonian paths in an n X k grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

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

A014585 Number of Hamiltonian paths in a 5 X n grid starting in the lower left corner and ending in the lower right.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A181689 Number of maximal self-avoiding walks from NW to SW corners of a 5 X n grid.

Views

Author

Keywords

Comments