A014584 -id:A014584 - cp's OEIS frontend

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.

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

A014523 Number of Hamiltonian paths in a 4 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 4, 20, 111, 624, 3505, 19676, 110444, 619935, 3479776, 19532449, 109638260, 615414276, 3454402959, 19390027600, 108838828241, 610926955724, 3429215026140, 19248644351551, 108045225087424, 606472354675265, 3404210752374756, 19108292005806324

Offset: 0

N. J. A. Sloane, Dec 11 1999

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Belgacem Bouras, A New Characterization of Catalan Numbers Related to Hankel Transforms and Fibonacci Numbers, Journal of Integer Sequences, 16 (2013), #13.3.3.
Karen L. Collins, Lucia B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Mathematics, Volume 169, Issues 1-3, 15 May 1997, Pages 29-38.
Michael Dougherty, Christopher French, Benjamin Saderholm, and Wenyang Qian, Hankel Transforms of Linear Combinations of Catalan Numbers, Journal of Integer Sequences, Vol. 14 (2011), Article 11.5.1.
Index entries for two-way infinite sequences
Index entries for sequences related to graphs, Hamiltonian
Index entries for linear recurrences with constant coefficients, signature (7,-9,7,-1).

Cf. A014584.

I:=[1,4,20,111]; [n le 4 select I[n] else 7*Self(n-1)- 9*Self(n-2)+7*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Dec 21 2015

CoefficientList[Series[(1 - 3 x + x^2)/(1 - 7 x + 9 x^2 - 7 x^3 + x^4), {x, 0, 50}], x] (* Vincenzo Librandi, Dec 21 2015 *)
LinearRecurrence[{7,-9,7,-1},{1,4,20,111},30] (* Harvey P. Dale, Jul 18 2024 *)

{a(n)= if(n<-1, -a(-2-n), polcoeff( (1-3*x+x^2)/ (1-7*x+9*x^2-7*x^3+x^4) +x*O(x^n), n))} /* Michael Somos, Jun 14 2003 */

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

a(n) = 7*a(n-1) - 9*a(n-2) + 7*a(n-3) - a(n-4) = -a(-2-n).

Sequence name clarified by Andrew Howroyd, Dec 20 2015

a(21)-a(22) from Vincenzo Librandi, Dec 21 2015

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

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

A333582 Number of Hamiltonian paths in a 7 X n grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 1, 32, 111, 1670, 10204, 111712, 851073, 8261289, 68939685, 637113287, 5521505724, 49977297839, 440051896440, 3947537767621, 34992551369200, 312684850861298, 2779712414621925, 24796726969942763, 220708765035288988, 1967401456946216789, 17520501580778152908

Offset: 1

Seiichi Manyama, Mar 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..500
Index entries for sequences related to graphs, Hamiltonian

Row n=7 of A333580.

Cf. A014584.

# 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()
def A333582(n):
    return A333580(n, 7)
print([A333582(n) for n in range(1, 25)])

A333584 Number of Hamiltonian paths in a 9 X n grid starting at the lower left corner and finishing in the upper right corner.

Original entry on oeis.org

1, 1, 128, 624, 28417, 286395, 8261289, 114243216, 2688307514, 43598351250, 928370853748, 16331387665387, 330593938169845, 6062963019120077, 119575303856316650, 2240422461856052342, 43592076562463162280, 825830699757513748579, 15955080499901505066753

Offset: 1

Seiichi Manyama, Mar 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Index entries for sequences related to graphs, Hamiltonian

Row n=9 of A333580.

Cf. A014584.

# 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()
def A333584(n):
    return A333580(n, 9)
print([A333584(n) for n in range(1, 20)])

cp's OEIS Frontend

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

A014523 Number of Hamiltonian paths in a 4 X (2n+1) grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

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

A333582 Number of Hamiltonian paths in a 7 X n grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A333584 Number of Hamiltonian paths in a 9 X n grid starting at the lower left corner and finishing in the upper right corner.

Views

Author

Keywords

Links

Crossrefs

Programs

Python