A339190
Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph.
Original entry on oeis.org
3, 4, 4, 8, 16, 8, 16, 120, 120, 16, 32, 744, 2830, 744, 32, 64, 4922, 50354, 50354, 4922, 64, 128, 31904, 1003218, 2462064, 1003218, 31904, 128, 256, 208118, 19380610, 139472532, 139472532, 19380610, 208118, 256, 512, 1354872, 378005474, 7621612496, 22853860116, 7621612496, 378005474, 1354872, 512
Offset: 2
Square array T(n,k) begins:
3, 4, 8, 16, 32, 64, ...
4, 16, 120, 744, 4922, 31904, ...
8, 120, 2830, 50354, 1003218, 19380610, ...
16, 744, 50354, 2462064, 139472532, 7621612496, ...
32, 4922, 1003218, 139472532, 22853860116, 3601249330324, ...
64, 31904, 19380610, 7621612496, 3601249330324, 1622043117414624, ...
-
# 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 A339190(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles(is_hamilton=True)
return cycles.len()
print([A339190(j + 2, i - j + 2) for i in range(10 - 1) for j in range(i + 1)])
A350729
Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.
Original entry on oeis.org
1, 1, 1, 1, 12, 1, 1, 48, 48, 1, 1, 208, 392, 208, 1, 1, 768, 4678, 4678, 768, 1, 1, 2752, 43676, 171592, 43676, 2752, 1, 1, 9472, 406396, 4743130, 4743130, 406396, 9472, 1, 1, 32000, 3568906, 132202038, 364618672, 132202038, 3568906, 32000, 1
Offset: 1
Array begins:
===========================================================
m\n | 1 2 3 4 5 6 ...
----+------------------------------------------------------
1 | 1 1 1 1 1 1 ...
2 | 1 12 48 208 768 2752 ...
3 | 1 48 392 4678 43676 406396 ...
4 | 1 208 4678 171592 4743130 132202038 ...
5 | 1 768 43676 4743130 364618672 28808442502 ...
6 | 1 2752 406396 132202038 28808442502 6544911081900 ...
...
A339198
Number of (undirected) cycles on the n X 4 king graph.
Original entry on oeis.org
85, 3459, 136597, 4847163, 171903334, 6109759868, 217211571195, 7721452793328, 274480808918598, 9757216290644264, 346848710800215246, 12329747938579785459, 438296805656767232863, 15580536695961884270466, 553855562644922140772689, 19688409342958501534182423
Offset: 2
-
# 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 A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
def A339198(n):
return A339098(n, 4)
print([A339198(n) for n in range(2, 20)])
A339199
Number of (undirected) cycles on the n X 5 king graph.
Original entry on oeis.org
204, 33145, 4847163, 545217435, 61575093671, 7050330616441, 808723201743855, 92672075290059017, 10617254793634907021, 1216460857186123433837, 139377550879455782939427, 15969325570952770252910697, 1829698785056144504575785405, 209639263869115933534540710701
Offset: 2
-
# 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 A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
def A339199(n):
return A339098(n, 5)
print([A339199(n) for n in range(2, 20)])
A339197
Number of (undirected) cycles on the n X 3 king graph.
Original entry on oeis.org
30, 348, 3459, 33145, 316164, 3013590, 28722567, 273751765, 2609096478, 24866992602, 237004387635, 2258860992595, 21528938911842, 205189789087374, 1955639788756293, 18638973217791295, 177645865363829526, 1693121885638023396, 16136945905019298321, 153799336805212613275
Offset: 2
-
# 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 A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
def A339197(n):
return A339098(n, 3)
print([A339197(n) for n in range(2, 30)])
A339196
Number of (undirected) cycles on the n X 2 king graph.
Original entry on oeis.org
7, 30, 85, 204, 451, 954, 1969, 4008, 8095, 16278, 32653, 65412, 130939, 262002, 524137, 1048416, 2096983, 4194126, 8388421, 16777020, 33554227, 67108650, 134217505, 268435224, 536870671, 1073741574, 2147483389, 4294967028, 8589934315, 17179868898, 34359738073, 68719476432
Offset: 2
-
# 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 A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
def A339196(n):
return A339098(n, 2)
print([A339196(n) for n in range(2, 30)])
Showing 1-6 of 6 results.