A338100 Number of spanning trees in the n X 2 king graph.

1, 16, 192, 2304, 27648, 331776, 3981312, 47775744, 573308928, 6879707136, 82556485632, 990677827584, 11888133931008, 142657607172096, 1711891286065152, 20542695432781824, 246512345193381888, 2958148142320582656, 35497777707846991872, 425973332494163902464, 5111679989929966829568

Offset: 1

Author

Seiichi Manyama, Nov 29 2020

Keywords

• nonn
• easy

Links

• Eric Weisstein's World of Mathematics, King Graph
• Eric Weisstein's World of Mathematics, Spanning Tree
• Index entries for linear recurrences with constant coefficients, signature (12).

Crossrefs

Column 2 of A338029.

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 A338029(n, k):
    if n == 1 or k == 1: return 1
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
def A338100(n):
    return A338029(n, 2)
print([A338100(n) for n in range(1, 20)])

Formula

a(n) = 12 * a(n-1) for n > 2.

a(n) = 3^(n-2) * 4^n for n > 1.

G.f.: x*(1 + 4*x)/(1 - 12*x). - Stefano Spezia, Nov 29 2020