A390791 Number of Hamiltonian paths from vertex (1, 1) to (3, 2*n+2) on the product graph C_4 X P_{2*n+2}, using (row, column) numbering.

6, 100, 1940, 38404, 760396, 15054372, 298045772, 5900697732, 116821771500, 2312832639460, 45789365703692, 906535983515716, 17947562207498284, 355325100215902116, 7034711755488051020, 139272934708897415172, 2757319847155996098924, 54589305204284332310884

Offset

0,1

Links

Seiichi Manyama, Table of n, a(n) for n = 0..200

Formula

Conjecture: G.f.: 2 * (3 - 13*x - 2*x^2)/(1 - 21*x + 26*x^2 - 44*x^3 + 8*x^4).

Prog

(Python)
# Using graphillion
from graphillion import GraphSet
def make_CnXPk(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))
    return grids
def A390791(n):
    universe = make_CnXPk(4, 2 * n + 2)
    GraphSet.set_universe(universe)
    start, goal = 1, 3 * (2 * n + 2)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A390791(n) for n in range(0, 18)])

Crossrefs

Cf. A003752.

Sequence in context: A226344 A395947 A278430 * A395298 A374889 A131311

Adjacent sequences: A390788 A390789 A390790 * A390792 A390793 A390794

Keyword

nonn

Author

Seiichi Manyama, Feb 12 2026

Status

approved