A333571 -id:A333571 - cp's OEIS frontend

A333574 Number of Hamiltonian paths in the n X 2 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.

1, 2, 4, 6, 10, 14, 20, 26, 34, 42, 52, 62, 74, 86, 100, 114, 130, 146, 164, 182, 202, 222, 244, 266, 290, 314, 340, 366, 394, 422, 452, 482, 514, 546, 580, 614, 650, 686, 724, 762, 802, 842, 884, 926, 970, 1014, 1060, 1106, 1154, 1202, 1252, 1302, 1354, 1406, 1460

Offset: 1

Seiichi Manyama, Mar 27 2020

Conjecture: Numbers k such that A339399(k) = A103128(k). - Wesley Ivan Hurt, Nov 19 2021

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

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Column k=2 of A333571.
Cf. A333510.
Cf. A103128, A339399.

N=66; x='x+O('x^N); Vec(x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)))

# 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 A333574(n):
    return A333571(n, 2)
print([A333574(n) for n in range(1, 25)])

G.f.: x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)).
From Colin Barker, Mar 27 2020: (Start)
a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n>5.
a(n) = (9 + (-1)^(1+n) - 4*n + 2*n^2) / 4 for n>1. (End)
E.g.f.: ((4 - x + x^2)*cosh(x) + (5 - x + x^2)*sinh(x) - 2*(2 + x))/2. - Stefano Spezia, Jun 14 2023

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

A333574 Number of Hamiltonian paths in the n X 2 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

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula