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.
1, 1, 1, 1, 16, 1, 1, 192, 192, 1, 1, 2304, 17745, 2304, 1, 1, 27648, 1612127, 1612127, 27648, 1, 1, 331776, 146356224, 1064918960, 146356224, 331776, 1, 1, 3981312, 13286470095, 698512774464, 698512774464, 13286470095, 3981312, 1
Offset: 1
Examples
Square array T(n,k) begins: 1, 1, 1, 1, 1, ... 1, 16, 192, 2304, 27648, ... 1, 192, 17745, 1612127, 146356224, ... 1, 2304, 1612127, 1064918960, 698512774464, ... 1, 27648, 146356224, 698512774464, 3271331573452800, ...
Links
- Eric Weisstein's World of Mathematics, King Graph
- Eric Weisstein's World of Mathematics, Spanning Tree
Crossrefs
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() print([A338029(j + 1, i - j + 1) for i in range(8) for j in range(i + 1)])
Formula
T(n,k) = T(k,n).