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,2

Comments

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

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Formula

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

Example

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

Prog

(PARI) N=66; x='x+O('x^N); Vec(x*(1+2*x*(1-x^2+x^3)/((1+x)*(1-x)^3)))
(Python)
# 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)])

Crossrefs

Column k=2 of A333571.

Cf. A333510.

Cf. A103128, A339399.

Sequence in context: A094589 A071425 A115065 * A008804 A001307 A322010

Adjacent sequences: A333571 A333572 A333573 * A333575 A333576 A333577

Keyword

nonn,easy

Author

Seiichi Manyama, Mar 27 2020

Status

approved