A003778 -id:A003778 - cp's OEIS frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

1, 4, 20, 276, 4324, 229348, 13535280, 3023313284, 745416341496, 730044829512632, 786671485270308848, 3452664855804347354220, 16652005717670534681315580, 331809088406733654427925292528, 7263611367960266490262600117251524

Offset: 1

David Bevan, Jul 19 2006

			From _Robert FERREOL_, Apr 03 2019: (Start)
a(3) = 20:
there are 4 paths similar to
  + - + - +
          |
  + - + - +
  |
  + - + - +
8 paths similar to
  + - + - +
  |       |
  +   + - +
  |   |
  +   + - +
and 8 paths similar to
  + - + - +
  |       |
  +   +   +
  |   |   |
  +   + - +
(End)

Jesper L. Jacobsen, Table of n, a(n) for n = 1..17
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
Index entries for sequences related to graphs, Hamiltonian

Main diagonal of A332307.
Cf. A003685, A003695, A003778, A145402.
Cf. A003763, A000532, A001184, A145157, A271507, A007764, A121785, A121789.

a(n) = A096969(n) / 2 for n > 1.

More terms from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007

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

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

A339763 Number of (undirected) Hamiltonian paths in the 5 X n king graph.

Original entry on oeis.org

1, 768, 43676, 4743130, 364618672, 28808442502, 2125185542510, 153198148096800, 10739936528121270, 738599412949227054, 49945111084852186032, 3331294312194018084810, 219599512046978073473186, 14331641424452867055092544, 927231520831830806024847178

Offset: 1

Seiichi Manyama, Dec 16 2020

nonn

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

Row 5 of A350729.

Cf. A003778, A308129, A339760, A339761, A339762.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def B(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339763(n):
    return B(n, 5)
print([A339763(n) for n in range(1, 11)])

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

cp's OEIS Frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

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

A339763 Number of (undirected) Hamiltonian paths in the 5 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

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