A338617
Number of spanning trees in the n X 4 king graph.
Original entry on oeis.org
1, 2304, 1612127, 1064918960, 698512774464, 457753027631164, 299940605530116319, 196531575367664678400, 128774089577828985307985, 84377085408032081020147412, 55286683084713553039968700608, 36225680193828279388607070447232, 23736274839549237072891352060244017
Offset: 1
-
# 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()
def A338617(n):
return A338029(n, 4)
print([A338617(n) for n in range(1, 20)])
A339257
Number of spanning trees in the n X 5 king graph.
Original entry on oeis.org
1, 27648, 146356224, 698512774464, 3271331573452800, 15258885095892902976, 71111090441547013886784, 331335100372867196224868352, 1543757070688065237574186369344, 7192607774929149127350811889484864, 33511424900308657559195109303117533184, 156134620449573478209362729027690283037248
Offset: 1
-
# 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()
def A339257(n):
return A338029(n, 5)
print([A339257(n) for n in range(1, 15)])
A338100
Number of spanning trees in the n X 2 king graph.
Original entry on oeis.org
1, 16, 192, 2304, 27648, 331776, 3981312, 47775744, 573308928, 6879707136, 82556485632, 990677827584, 11888133931008, 142657607172096, 1711891286065152, 20542695432781824, 246512345193381888, 2958148142320582656, 35497777707846991872, 425973332494163902464, 5111679989929966829568
Offset: 1
-
# 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()
def A338100(n):
return A338029(n, 2)
print([A338100(n) for n in range(1, 20)])
A338532
Number of spanning trees in the n X 3 king graph.
Original entry on oeis.org
1, 192, 17745, 1612127, 146356224, 13286470095, 1206167003329, 109497763028928, 9940381426772625, 902403667119137183, 81921642989758089216, 7436977302591050167695, 675140651246077550931841, 61290344237862763973468352, 5564035123440571957929508305, 505111975464406109413779799007
Offset: 1
-
# 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()
def A338532(n):
return A338029(n, 3)
print([A338532(n) for n in range(1, 20)])
Showing 1-4 of 4 results.