A302119 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,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

Author

Alois P. Heinz, Apr 01 2018

Keywords

• nonn
• easy

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5102
• 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)

Crossrefs

Cf. A069241, A293506, A293560, A302118.

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...