|
%I #14 Dec 09 2020 05:14:44
%S 8,120,2830,50354,1003218,19380610,378005474,7348400816,143013145124,
%T 2782280184314,54134923232608,1053263634537410,20492847566047336,
%U 398717839924458408,7757640305938339162,150936198726479633524,2936684182444832427774,57137476790772843457886
%N Number of (undirected) Hamiltonian cycles on the n X 4 king graph.
%H Seiichi Manyama, <a href="/A339201/b339201.txt">Table of n, a(n) for n = 2..500</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%F 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 (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o def make_nXk_king_graph(n, k):
%o grids = []
%o for i in range(1, k + 1):
%o for j in range(1, n):
%o grids.append((i + (j - 1) * k, i + j * k))
%o if i < k:
%o grids.append((i + (j - 1) * k, i + j * k + 1))
%o if i > 1:
%o grids.append((i + (j - 1) * k, i + j * k - 1))
%o for i in range(1, k * n, k):
%o for j in range(1, k):
%o grids.append((i + j - 1, i + j))
%o return grids
%o def A339190(n, k):
%o universe = make_nXk_king_graph(n, k)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles(is_hamilton=True)
%o return cycles.len()
%o def A339201(n):
%o return A339190(n, 4)
%o print([A339201(n) for n in range(2, 20)])
%Y Column 4 of A339190.
%Y Cf. A339198.
%K nonn
%O 2,1
%A _Seiichi Manyama_, Nov 27 2020
| 