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

Author

Seiichi Manyama, Nov 29 2020

Keywords

• nonn
• tabl

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

Rows and columns 1..5 give A000012, A338100, A338532, A338617, A339257.

Main diagonal gives A288957.

Cf. A116469.

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