A302118
Number of permutations p of [n] such that |p(i) - p(i-1)| is in {1,3} for all i from 2 to n.
Original entry on oeis.org
1, 1, 2, 2, 8, 12, 32, 40, 88, 118, 244, 338, 642, 912, 1650, 2402, 4182, 6200, 10492, 15786, 26166, 39814, 64994, 99738, 161020, 248670, 398248, 617912, 983890, 1531796, 2428988, 3790980, 5993746, 9371174, 14785512, 23146268, 36465816, 57137316, 89924384
Offset: 0
a(3) = 2: 123, 321.
a(4) = 8: 1234, 1432, 2143, 2341, 3214, 3412, 4123, 4321.
a(5) = 12: 12345, 12543, 14325, 14523, 32145, 32541, 34125, 34521, 52143, 52341, 54123, 54321.
- Alois P. Heinz, Table of n, a(n) for n = 0..5100
- Index entries for linear recurrences with constant coefficients, signature (1,3,-2,-1,-1,-3,1,1,3,1,1,0,-2,0,-1)
A069241
Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| <= 2.
Original entry on oeis.org
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
Offset: 0
For example, the six Hamiltonian paths when n=4 are 1234, 1243, 1324, 1342, 2134, 3124.
-
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
-
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 *)
Showing 1-2 of 2 results.
Comments