The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A069241 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j|<=2. 5
 1, 1, 1, 3, 6, 10, 17, 28, 44, 68, 104, 157, 235, 350, 519, 767, 1131, 1665, 2448, 3596, 5279, 7746, 11362, 16662, 24430, 35815, 52501, 76956, 112797, 165325, 242309, 355135, 520490, 762830, 1117997, 1638520, 2401384, 3519416, 5157972, 7559393, 11078847 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Equivalently, the number of bandwidth-at-most-2 arrangements of a straight line of n vertices. a(n) = A003274(n)/2, n>1. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..2000 Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1). FORMULA a(n) = 3s(n)+s(n-1)+s(n-2)-2-n, where s(n) = A000930(n). G.f.: (3+x+x^2)/(1-x-x^3)-(2-x)/(1-x)^2. limit_{n->infinity} a(n+1)/a(n) = A092526 = 1/A263719. - Alois P. Heinz, Apr 15 2018 EXAMPLE For example, the six Hamiltonian paths when n=4 are 1234, 1243, 1324, 1342, 2134, 3124. MAPLE 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 MATHEMATICA 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 *) 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 *) CROSSREFS Cf. A000930, A092526, A263719, A302119. Sequence in context: A286304 A005045 A189376 * A092263 A259968 A242525 Adjacent sequences:  A069238 A069239 A069240 * A069242 A069243 A069244 KEYWORD nonn,easy AUTHOR Don Knuth, Apr 13 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 20 10:00 EDT 2020. Contains 337900 sequences. (Running on oeis4.)