|
Search: id:A069241
|
|
|
| A069241 |
|
Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j|<=2. |
|
+0
4
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
Equivalently, the number of bandwidth-at-most-2 arrangements of a straight line of n vertices.
a(n) = A003274(n)/2, n>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.
|
|
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..38); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 09 2008]
|
|
CROSSREFS
|
Cf. A000930.
Sequence in context: A119971 A094272 A005045 this_sequence A092263 A076251 A029864
Adjacent sequences: A069238 A069239 A069240 this_sequence A069242 A069243 A069244
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
D. E. Knuth, Apr 13 2002
|
|
|
Search completed in 0.002 seconds
|
