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

Links

Table of n, a(n) for n=1..21.

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).

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

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 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)])

Crossrefs

Column 2 of A338029.

Sequence in context: A317601 A000767 A053539 * A218176 A120994 A016178

Adjacent sequences: A338097 A338098 A338099 * A338101 A338102 A338103

Keyword

nonn,easy

Author

Seiichi Manyama, Nov 29 2020

Status

approved