A338100 - OEIS

%I #53 Nov 29 2020 08:19:26

%S 1,16,192,2304,27648,331776,3981312,47775744,573308928,6879707136,

%T 82556485632,990677827584,11888133931008,142657607172096,

%U 1711891286065152,20542695432781824,246512345193381888,2958148142320582656,35497777707846991872,425973332494163902464,5111679989929966829568

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>

%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (12).

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

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

%F G.f.: x*(1 + 4*x)/(1 - 12*x). - _Stefano Spezia_, Nov 29 2020

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o def make_nXk_king_graph(n, k):

%o     grids = []

%o     for i in range(1, k + 1):

%o         for j in range(1, n):

%o             grids.append((i + (j - 1) * k, i + j * k))

%o             if i < k:

%o                 grids.append((i + (j - 1) * k, i + j * k + 1))

%o             if i > 1:

%o                 grids.append((i + (j - 1) * k, i + j * k - 1))

%o     for i in range(1, k * n, k):

%o         for j in range(1, k):

%o             grids.append((i + j - 1, i + j))

%o     return grids

%o def A338029(n, k):

%o     if n == 1 or k == 1: return 1

%o     universe = make_nXk_king_graph(n, k)

%o     GraphSet.set_universe(universe)

%o     spanning_trees = GraphSet.trees(is_spanning=True)

%o     return spanning_trees.len()

%o def A338100(n):

%o     return A338029(n, 2)

%o print([A338100(n) for n in range(1, 20)])

%Y Column 2 of A338029.

%K nonn,easy

%O 1,2

%A _Seiichi Manyama_, Nov 29 2020