A339196 Number of (undirected) cycles on the n X 2 king graph.

7, 30, 85, 204, 451, 954, 1969, 4008, 8095, 16278, 32653, 65412, 130939, 262002, 524137, 1048416, 2096983, 4194126, 8388421, 16777020, 33554227, 67108650, 134217505, 268435224, 536870671, 1073741574, 2147483389, 4294967028, 8589934315, 17179868898, 34359738073, 68719476432

Offset: 2

Author

Seiichi Manyama, Nov 27 2020

Keywords

• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 2..1000
• Eric Weisstein's World of Mathematics, Graph Cycle
• Eric Weisstein's World of Mathematics, King Graph

Crossrefs

Column 2 of A339098.

Programs

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 A339098(n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
def A339196(n):
    return A339098(n, 2)
print([A339196(n) for n in range(2, 30)])

Formula

Empirical g.f.: -x^2 * (7 + 2*x) / ((-1 + x)^2 * (-1 + 2*x)). - Vaclav Kotesovec, Dec 09 2020