|
|
A339200
|
|
Number of (undirected) Hamiltonian cycles on the n X 3 king graph.
|
|
4
|
|
|
4, 16, 120, 744, 4922, 31904, 208118, 1354872, 8826022, 57483536, 374412158, 2438639080, 15883563110, 103454037120, 673825180718, 4388811619032, 28585557862518, 186185731404016, 1212679737590398, 7898522254036168, 51445284278407878, 335077523213321312, 2182453613487235150, 14214930709900240312
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
LINKS
|
|
|
FORMULA
|
Empirical g.f.: 2*x^2 * (3*x^4 + 4*x^3 + 2*x^2 - 2) / (6*x^4 + 8*x^3 + 15*x^2 + 4*x - 1). - Vaclav Kotesovec, Dec 09 2020
|
|
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
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles(is_hamilton=True)
return cycles.len()
print([A339200(n) for n in range(2, 20)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|