|
|
A333602
|
|
Number of directed Hamiltonian walks from NW to SW corners of a 6 X n grid.
|
|
1
|
|
|
1, 1, 16, 47, 397, 1770, 11658, 59946, 359962, 1958968, 11341696, 63142224, 360314940, 2024278172, 11485023624, 64758162416, 366573071464, 2069908196378, 11706322628832, 66139560111600, 373914808423830, 2113066820134474, 11944325099736622, 67505931650135578
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (5,14,-63,12,90,-35,-66,118,-8,-82,42,28,-4,2).
|
|
FORMULA
|
a(n) = 5*a(n-1) + 14*a(n-2) - 63*a(n-3) + 12*a(n-4) + 90*a(n-5) - 35*a(n-6) - 66*a(n-7) + 118*a(n-8) - 8*a(n-9) - 82*a(n-10) + 42*a(n-11) + 28*a(n-12) - 4*a(n-13) + 2*a(n-14), n > 14. - Michael Gray, Jan 30 2022
G.f.: x*(1 - x)*(1 - 3*x - 6*x^2 + 10*x^3 - x^4 + 32*x^5 - 4*x^6 - 20*x^7 + 24*x^8 + 13*x^9 + 2*x^10 + 2*x^11)/(1 - 5*x - 14*x^2 + 63*x^3 - 12*x^4 - 90*x^5 + 35*x^6 + 66*x^7 - 118*x^8 + 8*x^9 + 82*x^10 - 42*x^11 - 28*x^12 + 4*x^13 - 2*x^14). - Andrew Howroyd, Jan 31 2022
|
|
PROG
|
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
if k == 1: return 1
universe = tl.grid(k - 1, n - 1)
GraphSet.set_universe(universe)
start, goal = 1, n
paths = GraphSet.paths(start, goal, is_hamilton=True)
return paths.len()
print([A333602(n) for n in range(1, 10)])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,walk
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|