A339760 Number of (undirected) Hamiltonian paths in the 2 X n king graph.
1, 12, 48, 208, 768, 2752, 9472, 32000, 106496, 351232, 1150976, 3756032, 12222464, 39698432, 128778240, 417398784, 1352138752, 4378591232, 14175698944, 45886734336, 148520304640, 480679821312, 1555633799168, 5034389536768, 16292153131008, 52723609239552, 170619454881792, 552140862914560
Offset: 1
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..500 (terms 1..50 from Seiichi Manyama)
- Eric Weisstein's World of Mathematics, Graph Path
- Eric Weisstein's World of Mathematics, King Graph
- Index entries for linear recurrences with constant coefficients, signature (6,-8,-8,16).
Programs
-
PARI
Vec((1 + 6*x - 16*x^2 + 24*x^3 - 16*x^4) / ((1 - 2*x)^2 * (1 - 2*x - 4*x^2)) + O(x^20)) \\ Andrew Howroyd, Jan 17 2022
-
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 def A(start, goal, n, k): universe = make_nXk_king_graph(n, k) GraphSet.set_universe(universe) paths = GraphSet.paths(start, goal, is_hamilton=True) return paths.len() def B(n, k): m = k * n s = 0 for i in range(1, m): for j in range(i + 1, m + 1): s += A(i, j, n, k) return s def A339760(n): return B(n, 2) print([A339760(n) for n in range(1, 21)])
Formula
Empirical g.f.: x*(1 + 6*x - 16*x^2 + 24*x^3 - 16*x^4) / ((1 - 2*x)^2 * (1 - 2*x - 4*x^2)). - Vaclav Kotesovec, Dec 16 2020
The above formula is correct. - Andrew Howroyd, Jan 17 2022