A003685 -id:A003685 - 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).

A339761 Number of (undirected) Hamiltonian paths in the 3 X n king graph.

Original entry on oeis.org

1, 48, 392, 4678, 43676, 406396, 3568906, 30554390, 254834078, 2085479610, 16791859330, 133416458104, 1048095087616, 8154539310958, 62918331433308, 481954854686434, 3668399080453520, 27766093432542984, 209120844634276158, 1568050593805721822

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
Index entries for linear recurrences with constant coefficients, signature (15,-36,-289,708,2617,-1278,-4641,2263,4808,3286,-1422,-3830,-2200, -432,216,216).

Row 3 of A350729.

Cf. A003685, A308129, A339751, A339760, A339762, A339763.

# 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 A339761(n):
    return B(n, 3)
print([A339761(n) for n in range(1, 11)])

G.f.: x*(1 + 33*x - 292*x^2 + 815*x^3 + 782*x^4 - 3649*x^5 - 4630*x^6 + 1517*x^7 + 3835*x^8 - 3822*x^9 - 5722*x^10 - 5418*x^11 - 7562*x^12 - 4808*x^13 - 240*x^14 + 720*x^15 + 216*x^16)/((1 - x)*(1 - 4*x - 15*x^2 - 8*x^3 - 6*x^4)^2*(1 - 6*x - 12*x^2 + 27*x^3 - 2*x^4 - 30*x^5 - 4*x^6 + 6*x^7)). - Andrew Howroyd, Jan 17 2022

A339797 Number of (undirected) Hamiltonian paths in the graph C_3 X C_n.

Original entry on oeis.org

756, 4128, 18240, 73368, 277536, 1001760, 3512160, 12009480, 40390944, 133893936, 439304736, 1428450072, 4613176800, 14809528896, 47315578848, 150534443304, 477237381024, 1508232832080, 4753573999776, 14945425070136, 46886868887136, 146802927436128, 458818252975200

Offset: 3

Seiichi Manyama, Dec 17 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 3..50
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Torus Grid Graph

Cf. A003685, A268838, A339795, A339798.

# Using graphillion
from graphillion import GraphSet
def make_CnXCk(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))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
        grids.append((i + k - 1, i))
    return grids
def A(start, goal, n, k):
    universe = make_CnXCk(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 A339797(n):
    return B(n, 3)
print([A339797(n) for n in range(3, 10)])

A333575 Number of Hamiltonian paths in the n X 3 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

Original entry on oeis.org

1, 2, 8, 14, 38, 74, 170, 338, 724, 1448, 3000, 6008, 12240, 24512, 49504, 99104, 199232, 398720, 799616, 1599872, 3204352, 6410240, 12830208, 25664000, 51348480, 102705152, 205453312, 410925056, 821940224, 1643921408, 3288031232, 6576152576, 13152698368, 26305593344

Offset: 1

Seiichi Manyama, Mar 27 2020

			a(1) = 1;
   +--*--+
a(2) = 2;
   +  *--*   *--*  +
   |  |  |   |  |  |
   *--*  +   +  *--*

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (2,4,-8,-4,8).

Column k=3 of A333571.

Cf. A003685, A333511.

Vec(x*(1 - 2*x^3 - 2*x^4 + 6*x^5 - 2*x^6 - 2*x^7) / ((1 - 2*x)*(1 - 2*x^2)^2) + O(x^40)) \\ Colin Barker, Mar 29 2020

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

G.f.: x*(1+2*x*(1+x*(4-x-11*x^2+3*x^3+7*x^4-x^5) / ((1-2*x)*(1-2*x^2)^2))). [Confirmed by Andrew Howroyd, Mar 27 2020]

a(n) = 2*a(n-1) + 4*a(n-2) - 8*a(n-3) - 4*a(n-4) + 8*a(n-5) for n>8. - Colin Barker, Mar 27 2020 [Confirmed by Andrew Howroyd, Mar 27 2020]

Terms a(22) and beyond from Andrew Howroyd, Mar 27 2020

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

A339761 Number of (undirected) Hamiltonian paths in the 3 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A339797 Number of (undirected) Hamiltonian paths in the graph C_3 X C_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A333575 Number of Hamiltonian paths in the n X 3 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions