|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
LINKS
|
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).
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
|
|
|
STATUS
|
approved
|
|
|
|