A339200 Number of (undirected) Hamiltonian cycles on the n X 3 king graph.

4, 16, 120, 744, 4922, 31904, 208118, 1354872, 8826022, 57483536, 374412158, 2438639080, 15883563110, 103454037120, 673825180718, 4388811619032, 28585557862518, 186185731404016, 1212679737590398, 7898522254036168, 51445284278407878, 335077523213321312, 2182453613487235150, 14214930709900240312

Offset

2,1

Links

Seiichi Manyama, Table of n, a(n) for n = 2..1000

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Eric Weisstein's World of Mathematics, King Graph

Index entries for sequences related to graphs, Hamiltonian

Formula

Empirical g.f.: 2*x^2 * (3*x^4 + 4*x^3 + 2*x^2 - 2) / (6*x^4 + 8*x^3 + 15*x^2 + 4*x - 1). - Vaclav Kotesovec, Dec 09 2020

Prog

(Python)
# 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 A339190(n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
def A339200(n):
    return A339190(n, 3)
print([A339200(n) for n in range(2, 20)])

Crossrefs

Column 3 of A339190.

Cf. A339197.

Sequence in context: A356130 A210573 A337040 * A087335 A204573 A358880

Adjacent sequences: A339197 A339198 A339199 * A339201 A339202 A339203

Keyword

nonn

Author

Seiichi Manyama, Nov 27 2020

Status

approved