login
A302119
Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,3}.
3
1, 1, 1, 1, 4, 6, 16, 20, 44, 59, 122, 169, 321, 456, 825, 1201, 2091, 3100, 5246, 7893, 13083, 19907, 32497, 49869, 80510, 124335, 199124, 308956, 491945, 765898, 1214494, 1895490, 2996873, 4685587, 7392756, 11573134, 18232908, 28568658, 44962192, 70494629
OFFSET
0,5
LINKS
Eric Weisstein's World of Mathematics, Hamiltonian path
Wikipedia, Hamiltonian path
Index entries for linear recurrences with constant coefficients, signature (1,3,-2,-1,-1,-3,1,1,3,1,1,0,-2,0,-1)
FORMULA
G.f.: (x^16 -x^15 +x^13 +x^12 +2*x^11 -x^10 -5*x^9 -6*x^8 -2*x^7 +5*x^6 +3*x^5 +3*x^4 -x^3 -3*x^2+1) / ((x-1) *(x+1) *(x^5+x^3+x-1) *(x^4+x^2-1)^2).
a(n) = ceiling(A302118(n)/2).
limit_{n->infinity} a(n)/a(n+1) = A293560 = 1/A293506 = 0.63688291680184484849...
EXAMPLE
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 1: 123.
a(4) = 4: 1234, 1432, 2143, 3214.
a(5) = 6: 12345, 12543, 14325, 14523, 32145, 34125.
a(6) = 16: 123456, 123654, 125436, 125634, 143256, 143652, 145236, 145632, 214365, 214563, 321456, 341256, 365214, 412365, 521436, 541236.
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Apr 01 2018
STATUS
approved