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

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 2, 1, 1, 0, 1, 0, 4, 0, 1, 0, 1, 4, 8, 8, 1, 1, 0, 1, 0, 23, 0, 16, 0, 1, 0, 1, 8, 55, 86, 47, 32, 1, 1, 0, 1, 0, 144, 0, 397, 0, 64, 0, 1, 0, 1, 16, 360, 948, 1770, 1584, 264, 128, 1, 1, 0, 1, 0, 921, 0, 11658, 0, 6820, 0, 256, 0, 1

Offset: 1

Andrew Howroyd, Apr 10 2016

			The start of the sequence as table:
* 1 0   0   0     0     0       0       0          0 ...
* 1 1   1   1     1     1       1       1          1 ...
* 1 0   2   0     4     0       8       0         16 ...
* 1 1   4   8    23    55     144     360        921 ...
* 1 0   8   0    86     0     948       0      10444 ...
* 1 1  16  47   397  1770   11658   59946     359962 ...
* 1 0  32   0  1584     0   88418       0    4999752 ...
* 1 1  64 264  6820 52387  909009 8934966  130373192 ...
* 1 0 128   0 28002     0 7503654       0 2087813834 ...
* ...

Andrew Howroyd, Antidiagonals n = 1..27, flattened

Column 4 is aerated A014524, column 5 is A014585.
Rows include A181688, A181689.
Main diagonal is A000532.
Cf. A333580.

# 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()
print([A271592(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])  # Seiichi Manyama, Mar 28 2020

T(n,m)=0 for n odd and m even, T(1,n)=0 for n>1.

T(2,n)=T(n,1)=T(2*n,2)=1, T(3,2*n+1)=T(n+1,3)=2^n.

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

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

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

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