cp's OEIS Frontend

A338029 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of spanning trees in the n X k king graph.

%I A338029 #58 Feb 16 2025 08:34:00
%S A338029 1,1,1,1,16,1,1,192,192,1,1,2304,17745,2304,1,1,27648,1612127,1612127,
%T A338029 27648,1,1,331776,146356224,1064918960,146356224,331776,1,1,3981312,
%U A338029 13286470095,698512774464,698512774464,13286470095,3981312,1
%N A338029 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of spanning trees in the n X k king graph.
%H A338029 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%H A338029 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>
%F A338029 T(n,k) = T(k,n).
%e A338029 Square array T(n,k) begins:
%e A338029   1,     1,         1,            1,                1, ...
%e A338029   1,    16,       192,         2304,            27648, ...
%e A338029   1,   192,     17745,      1612127,        146356224, ...
%e A338029   1,  2304,   1612127,   1064918960,     698512774464, ...
%e A338029   1, 27648, 146356224, 698512774464, 3271331573452800, ...
%o A338029 (Python)
%o A338029 # Using graphillion
%o A338029 from graphillion import GraphSet
%o A338029 def make_nXk_king_graph(n, k):
%o A338029     grids = []
%o A338029     for i in range(1, k + 1):
%o A338029         for j in range(1, n):
%o A338029             grids.append((i + (j - 1) * k, i + j * k))
%o A338029             if i < k:
%o A338029                 grids.append((i + (j - 1) * k, i + j * k + 1))
%o A338029             if i > 1:
%o A338029                 grids.append((i + (j - 1) * k, i + j * k - 1))
%o A338029     for i in range(1, k * n, k):
%o A338029         for j in range(1, k):
%o A338029             grids.append((i + j - 1, i + j))
%o A338029     return grids
%o A338029 def A338029(n, k):
%o A338029     if n == 1 or k == 1: return 1
%o A338029     universe = make_nXk_king_graph(n, k)
%o A338029     GraphSet.set_universe(universe)
%o A338029     spanning_trees = GraphSet.trees(is_spanning=True)
%o A338029     return spanning_trees.len()
%o A338029 print([A338029(j + 1, i - j + 1) for i in range(8) for j in range(i + 1)])
%Y A338029 Rows and columns 1..5 give A000012, A338100, A338532, A338617, A339257.
%Y A338029 Main diagonal gives A288957.
%Y A338029 Cf. A116469.
%K A338029 nonn,tabl
%O A338029 1,5
%A A338029 _Seiichi Manyama_, Nov 29 2020