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.

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

Author

Alois P. Heinz, Apr 01 2018

Keywords

• nonn
• easy

Examples

			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.
		

Links

• 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)

Crossrefs

Cf. A003274, A174700, A293506, A293560, A302119, A307269, A328648.

Formula

G.f.: (x^16 -3*x^15 -2*x^14 +3*x^12 +6*x^11 +2*x^10 -6*x^9 -10*x^8 -6*x^7 +6*x^6 +4*x^5 +3*x^4 -x^3 -2*x^2+1) / ((x-1) *(x+1) *(x^5+x^3+x-1) *(x^4+x^2-1)^2).

a(n) = 2 * A302119(n) for n > 1.

Limit_{n->infinity} a(n)/a(n+1) = A293560 = 1/A293506 = 0.63688291680184484849...