A181688 -id:A181688 - 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.

A006864 Number of Hamiltonian cycles in P_4 X P_n.

Original entry on oeis.org

0, 1, 2, 6, 14, 37, 92, 236, 596, 1517, 3846, 9770, 24794, 62953, 159800, 405688, 1029864, 2614457, 6637066, 16849006, 42773094, 108584525, 275654292, 699780452, 1776473532, 4509783909, 11448608270, 29063617746, 73781357746, 187302518353, 475489124976, 1207084188912

Offset: 1

kwong(AT)cs.fredonia.edu (Harris Kwong), N. J. A. Sloane, Simon Plouffe and Frans J. Faase

Wazir tours on a 4 X n grid. There are two closed loops for a 4x4 board, appearing as an H and a C, for example. - Ed Pegg Jr, Sep 07 2010

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
Kwong, Y. H. H.; Enumeration of Hamiltonian cycles in P_4 X P_n and P_5 X P_n. Ars Combin. 33 (1992), 87-96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Huaide Cheng, Table of n, a(n) for n = 1..2473
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
C. Flye Sainte-Marie, Manières différentes de tracer une route fermée ..., L'Intermédiaire des Mathématiciens, vol. 11 (1904), pp. 86-88 (in French).
George Jelliss, Wazir Wanderings
R. Tosic, O. Bodroza, Y. H. Harris Kwong, and H. Joseph Straight, On the number of Hamiltonian cycles of P4 X Pn, Indian J. Pure Appl. Math. 21 (5) (1990), 403-409.
Index entries for linear recurrences with constant coefficients, signature (2,2,-2,1).

Row/column 4 of A321172.

LinearRecurrence[{2, 2, -2, 1}, {0, 1, 2, 6}, 50] (* Paolo Xausa, Jul 01 2025 *)

a(n):=sum ( sum ( binomial(k,j) *sum (binomial(j, i-j)*2^j *binomial(k-j,n-i-3*(k-j))*(-2)^(4*(k-j)-(n-i)), i,j,n-k+j) , j,0,k) , k,1,n ); /* Vladimir Kruchinin, Aug 04 2010 */

a(n) = 2*a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-4).
G.f.: x^2/(1-2x-2x^2+2x^3-x^4). - R. J. Mathar, Dec 16 2008
a(n)=sum ( sum ( binomial(k,j) * sum (binomial(j, i-j)*2^j *binomial(k-j,n-i-3*(k-j))*(-2)^(4*(k-j)-(n-i)), i,j,n-k+j) , j,0,k) , k,1,n ), n>0. - Vladimir Kruchinin, Aug 04 2010
a(n) = Sum_{k=1..n-1} A181688(k). - Kevin McShane, Aug 04 2019

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

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Original entry on oeis.org

1, 8, 38, 178, 844, 4012, 19072, 90658, 430938, 2048450, 9737260, 46285868, 220018976, 1045856010, 4971456754, 23631725866, 112332963420, 533972624844, 2538228811648, 12065422836242, 57352760145834, 272625264866098, 1295919060481740, 6160126839867820

Offset: 1

Toby Gottfried, Mar 09 2013

			For n=2, and moves U(p), D(own), R(ight), L(eft), the a(2)=8 walks are {DDD, DRDDL, DRDLD, DDRDL, RDDDL, RDDLD, RDLDD, RDLDRDL} with only the last touching all 8 squares of the grid.
Illustration of the 8 walks of a(2):
    .__      __      __        .       .        .       .     __
     __|    .  |    .  |    |__     |__      |  .    |  .     __|
    |  .     __|    .  |     __|     . |     |__     |  .    |__
    |  .    |  .     __|    |  .     __|      __|    |  .     __|

Andrew Howroyd, Table of n, a(n) for n = 1..100

Row 4 of A271465.
Cf. A181688 (maximal walks with same conditions).
Cf. A005409 (grids with 3 rows), A006189 (grids with 3 columns).
Cf. A216211 (grids with 4 columns).

Empirical recurrence: a(1,...,5) = (1, 8, 38, 178, 844), a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5). - Giovanni Resta, Mar 13 2013

Empirical g.f.: x*(1+x-6*x^2+x^3+x^4)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5). - Bruno Berselli, Mar 13 2013

Missing a(7) and a(13)-a(14) from Giovanni Resta, Mar 13 2013

a(15)-a(24) from Andrew Howroyd, Apr 08 2016

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

A006864 Number of Hamiltonian cycles in P_4 X P_n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

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

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions