%I #29 Sep 03 2021 05:55:24
%S 1,1,1,3,6,10,17,28,44,68,104,157,235,350,519,767,1131,1665,2448,3596,
%T 5279,7746,11362,16662,24430,35815,52501,76956,112797,165325,242309,
%U 355135,520490,762830,1117997,1638520,2401384,3519416,5157972,7559393,11078847
%N Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| <= 2.
%C Equivalently, the number of bandwidth-at-most-2 arrangements of a straight line of n vertices.
%H Alois P. Heinz, <a href="/A069241/b069241.txt">Table of n, a(n) for n = 0..2000</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,2,-2,1).
%F a(n) = A003274(n)/2, n > 1.
%F a(n) = 3*s(n) + s(n-1) + s(n-2) - 2 - n, where s(n) = A000930(n).
%F G.f.: (3+x+x^2)/(1-x-x^3) - (2-x)/(1-x)^2.
%F Lim_{n->infinity} a(n+1)/a(n) = A092526 = 1/A263719. - _Alois P. Heinz_, Apr 15 2018
%e For example, the six Hamiltonian paths when n=4 are 1234, 1243, 1324, 1342, 2134, 3124.
%p a:= n-> (Matrix([[1,1,1,0,1]]). Matrix(5, (i,j)-> if i=j-1 then 1 elif j=1 then [3,-3,2,-2,1][i] else 0 fi)^n)[1,3]: seq(a(n), n=0..50); # _Alois P. Heinz_, Sep 09 2008
%t a[0] = a[1] = a[2] = 1; a[3] = 3; a[4] = 6; a[n_] := a[n] = 3a[n-1] - 3a[n-2] + 2a[n-3] - 2a[n-4] + a[n-5]; Table[a[n], {n, 0, 38}] (* _Jean-François Alcover_, Feb 13 2015 *)
%t CoefficientList[Series[(3+x+x^2)/(1-x-x^3)-(2-x)/(1-x)^2,{x,0,60}],x] (* or *) LinearRecurrence[{3,-3,2,-2,1},{1,1,1,3,6},60] (* _Harvey P. Dale_, Apr 07 2019 *)
%Y Cf. A003274, A000930, A092526, A263719, A302119.
%K nonn,easy
%O 0,4
%A _Don Knuth_, Apr 13 2002