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,5

Links

Table of n, a(n) for n=1..36.

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Spanning Tree

Formula

T(n,k) = T(k,n).

Example

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

Prog

(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)])

Crossrefs

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

Main diagonal gives A288957.

Cf. A116469.

Sequence in context: A177823 A142462 A203397 * A173885 A173585 A022179

Adjacent sequences: A338026 A338027 A338028 * A338030 A338031 A338032

Keyword

nonn,tabl

Author

Seiichi Manyama, Nov 29 2020

Status

approved