cp's OEIS Frontend

A069241 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| <= 2.

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