cp's OEIS Frontend

A302119 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,3}.

%I A302119 #18 Feb 16 2025 08:33:53
%S A302119 1,1,1,1,4,6,16,20,44,59,122,169,321,456,825,1201,2091,3100,5246,7893,
%T A302119 13083,19907,32497,49869,80510,124335,199124,308956,491945,765898,
%U A302119 1214494,1895490,2996873,4685587,7392756,11573134,18232908,28568658,44962192,70494629
%N A302119 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,3}.
%H A302119 Alois P. Heinz, <a href="/A302119/b302119.txt">Table of n, a(n) for n = 0..5102</a>
%H A302119 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian path</a>
%H A302119 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>
%H A302119 <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-2,-1,-1,-3,1,1,3,1,1,0,-2,0,-1)
%F A302119 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).
%F A302119 a(n) = ceiling(A302118(n)/2).
%F A302119 limit_{n->infinity} a(n)/a(n+1) = A293560 = 1/A293506 = 0.63688291680184484849...
%e A302119 a(1) = 1: 1.
%e A302119 a(2) = 1: 12.
%e A302119 a(3) = 1: 123.
%e A302119 a(4) = 4: 1234, 1432, 2143, 3214.
%e A302119 a(5) = 6: 12345, 12543, 14325, 14523, 32145, 34125.
%e A302119 a(6) = 16: 123456, 123654, 125436, 125634, 143256, 143652, 145236, 145632, 214365, 214563, 321456, 341256, 365214, 412365, 521436, 541236.
%Y A302119 Cf. A069241, A293506, A293560, A302118.
%K A302119 nonn,easy
%O A302119 0,5
%A A302119 _Alois P. Heinz_, Apr 01 2018