cp's OEIS Frontend

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

%I A338100 #54 Feb 16 2025 08:34:00
%S A338100 1,16,192,2304,27648,331776,3981312,47775744,573308928,6879707136,
%T A338100 82556485632,990677827584,11888133931008,142657607172096,
%U A338100 1711891286065152,20542695432781824,246512345193381888,2958148142320582656,35497777707846991872,425973332494163902464,5111679989929966829568
%N A338100 Number of spanning trees in the n X 2 king graph.
%H A338100 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%H A338100 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>
%H A338100 <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (12).
%F A338100 a(n) = 12 * a(n-1) for n > 2.
%F A338100 a(n) = 3^(n-2) * 4^n for n > 1.
%F A338100 G.f.: x*(1 + 4*x)/(1 - 12*x). - _Stefano Spezia_, Nov 29 2020
%o A338100 (Python)
%o A338100 # Using graphillion
%o A338100 from graphillion import GraphSet
%o A338100 def make_nXk_king_graph(n, k):
%o A338100     grids = []
%o A338100     for i in range(1, k + 1):
%o A338100         for j in range(1, n):
%o A338100             grids.append((i + (j - 1) * k, i + j * k))
%o A338100             if i < k:
%o A338100                 grids.append((i + (j - 1) * k, i + j * k + 1))
%o A338100             if i > 1:
%o A338100                 grids.append((i + (j - 1) * k, i + j * k - 1))
%o A338100     for i in range(1, k * n, k):
%o A338100         for j in range(1, k):
%o A338100             grids.append((i + j - 1, i + j))
%o A338100     return grids
%o A338100 def A338029(n, k):
%o A338100     if n == 1 or k == 1: return 1
%o A338100     universe = make_nXk_king_graph(n, k)
%o A338100     GraphSet.set_universe(universe)
%o A338100     spanning_trees = GraphSet.trees(is_spanning=True)
%o A338100     return spanning_trees.len()
%o A338100 def A338100(n):
%o A338100     return A338029(n, 2)
%o A338100 print([A338100(n) for n in range(1, 20)])
%Y A338100 Column 2 of A338029.
%K A338100 nonn,easy
%O A338100 1,2
%A A338100 _Seiichi Manyama_, Nov 29 2020