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

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

Formula

Empirical g.f.: -x^2 * (7 + 2*x) / ((-1 + x)^2 * (-1 + 2*x)). - 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 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)])

Crossrefs

Column 2 of A339098.

Sequence in context: A083474 A030440 A256225 * A232093 A045889 A038739

Adjacent sequences: A339193 A339194 A339195 * A339197 A339198 A339199

Keyword

nonn

Author

Seiichi Manyama, Nov 27 2020

Status

approved