cp's OEIS Frontend

A339201 Number of (undirected) Hamiltonian cycles on the n X 4 king graph.

%I A339201 #15 Feb 16 2025 08:34:01
%S A339201 8,120,2830,50354,1003218,19380610,378005474,7348400816,143013145124,
%T A339201 2782280184314,54134923232608,1053263634537410,20492847566047336,
%U A339201 398717839924458408,7757640305938339162,150936198726479633524,2936684182444832427774,57137476790772843457886
%N A339201 Number of (undirected) Hamiltonian cycles on the n X 4 king graph.
%H A339201 Seiichi Manyama, <a href="/A339201/b339201.txt">Table of n, a(n) for n = 2..500</a>
%H A339201 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H A339201 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%H A339201 <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%F A339201 Empirical g.f.: 2*x^2 * (56*x^16 + 53*x^15 + 413*x^14 - 943*x^13 - 635*x^12 - 700*x^11 + 2283*x^10 + 455*x^9 + 3044*x^8 - 4856*x^7 - 4293*x^6 + 6475*x^5 + 719*x^4 - 1386*x^3 + 143*x^2 - 8*x + 4) / (112*x^16 + 106*x^15 + 964*x^14 - 1933*x^13 + 357*x^12 - 3503*x^11 + 3756*x^10 - 828*x^9 + 12662*x^8 - 18201*x^7 - 2441*x^6 + 5486*x^5 - 704*x^4 + 318*x^3 - 63*x^2 - 17*x + 1). - _Vaclav Kotesovec_, Dec 09 2020
%o A339201 (Python)
%o A339201 # Using graphillion
%o A339201 from graphillion import GraphSet
%o A339201 def make_nXk_king_graph(n, k):
%o A339201     grids = []
%o A339201     for i in range(1, k + 1):
%o A339201         for j in range(1, n):
%o A339201             grids.append((i + (j - 1) * k, i + j * k))
%o A339201             if i < k:
%o A339201                 grids.append((i + (j - 1) * k, i + j * k + 1))
%o A339201             if i > 1:
%o A339201                 grids.append((i + (j - 1) * k, i + j * k - 1))
%o A339201     for i in range(1, k * n, k):
%o A339201         for j in range(1, k):
%o A339201             grids.append((i + j - 1, i + j))
%o A339201     return grids
%o A339201 def A339190(n, k):
%o A339201     universe = make_nXk_king_graph(n, k)
%o A339201     GraphSet.set_universe(universe)
%o A339201     cycles = GraphSet.cycles(is_hamilton=True)
%o A339201     return cycles.len()
%o A339201 def A339201(n):
%o A339201     return A339190(n, 4)
%o A339201 print([A339201(n) for n in range(2, 20)])
%Y A339201 Column 4 of A339190.
%Y A339201 Cf. A339198.
%K A339201 nonn
%O A339201 2,1
%A A339201 _Seiichi Manyama_, Nov 27 2020