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.
Original entry on oeis.org
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
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, ...
-
# 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)])
A339198
Number of (undirected) cycles on the n X 4 king graph.
Original entry on oeis.org
85, 3459, 136597, 4847163, 171903334, 6109759868, 217211571195, 7721452793328, 274480808918598, 9757216290644264, 346848710800215246, 12329747938579785459, 438296805656767232863, 15580536695961884270466, 553855562644922140772689, 19688409342958501534182423
Offset: 2
-
# 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 A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
def A339198(n):
return A339098(n, 4)
print([A339198(n) for n in range(2, 20)])
A339851
Number of Hamiltonian circuits within parallelograms of size 4 X n on the triangular lattice.
Original entry on oeis.org
1, 13, 80, 549, 3851, 26499, 183521, 1269684, 8782833, 60764640, 420375910, 2908245096, 20119820809, 139192751951, 962962619849, 6661962019139, 46088745527485, 318850883829314, 2205872265781839, 15260652269262421, 105576152878533354, 730396306808551777, 5053023343572544589
Offset: 2
- Seiichi Manyama, Table of n, a(n) for n = 2..1000
- M. Peto, Studies of protein designability using reduced models, Thesis, 2007.
- Index entries for linear recurrences with constant coefficients, signature (3,21,44,-5,-47,-26,83,-81,39,-10,1)
-
CoefficientList[Series[x^2(1+10x+20x^2-8x^3-43x^4+9x^5+34x^6-42x^7+24x^8-7x^9+x^10)/(1-3x-21x^2-44x^3+5x^4+47x^5+26x^6-83x^7+81x^8-39x^9+10x^10-x^11),{x,0,30}],x] (* or *) LinearRecurrence[{3,21,44,-5,-47,-26,83,-81,39,-10,1},{1,13,80,549,3851,26499,183521,1269684,8782833,60764640,420375910},30] (* Harvey P. Dale, Mar 30 2023 *)
-
N=40; a=vector(N); a[2]=1; a[3]=13; a[4]=80; a[5]=549; a[6]=3851; a[7]=26499; a[8]=183521; a[9]=1269684; a[10]=8782833; a[11]=60764640; a[12]=420375910; for(n=13, N, a[n]=3*a[n-1]+21*a[n-2]+44*a[n-3]-5*a[n-4]-47*a[n-5]-26*a[n-6]+83*a[n-7]-81*a[n-8]+39*a[n-9]-10*a[n-10]+a[n-11]); a[2..N]
-
# Using graphillion
from graphillion import GraphSet
def make_T_nk(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))
for i in range(1, k * n, k):
for j in range(1, k):
grids.append((i + j - 1, i + j))
return grids
def A339849(n, k):
universe = make_T_nk(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles(is_hamilton=True)
return cycles.len()
def A339851(n):
return A339849(4, n)
print([A339851(n) for n in range(2, 21)])
A358626
Number of (undirected) paths in the 4 X n king graph.
Original entry on oeis.org
6, 1448, 96956, 6014812, 329967798, 16997993692, 834776217484, 39563650279918, 1823748204789500, 82228567227405462, 3641260776226602674, 158852482151721371580, 6843583319011989465314, 291698433877308327463184
Offset: 1
Showing 1-4 of 4 results.