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.
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
Examples
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, ...
Links
- Seiichi Manyama, Antidiagonals n = 2..12, flattened
- Eric Weisstein's World of Mathematics, Hamiltonian Cycle
- Eric Weisstein's World of Mathematics, King Graph
- Index entries for sequences related to graphs, Hamiltonian
Crossrefs
Programs
-
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 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)])
Formula
T(n,k) = T(k,n).