A333833 Number of permutations p of [n] such that |p(i) - p(i-1)| <= 2 and |p(i) - p(i-2)| <= 3.

1, 1, 2, 6, 12, 14, 18, 28, 42, 56, 74, 102, 144, 200, 274, 376, 520, 720, 994, 1370, 1890, 2610, 3604, 4974, 6864, 9474, 13078, 18052, 24916, 34390, 47468, 65520, 90436, 124826, 172294, 237814, 328250, 453076, 625370, 863184, 1191434, 1644510, 2269880, 3133064

Offset: 0

Author

Alois P. Heinz, Apr 07 2020

Keywords

• nonn
• easy

Examples

			a(5) = 14: 12345, 12354, 12435, 12453, 13245, 21345, 31245, 35421, 45321, 53421, 54213, 54231, 54312, 54321.
a(6) = 18: 123456, 123465, 123546, 123564, 124356, 132456, 213456, 213465, 312456, 465321, 564312, 564321, 645321, 653421, 654213, 654231, 654312, 654321.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..7141
• Alois P. Heinz, Animation of a(10) = 74 permutations
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Crossrefs

Cf. A003274, A086106, A174700, A263690, A263696, A302510, A307269, A328648, A338614.

Programs

Mathematica

Join[{1, 1, 2, 6, 12}, LinearRecurrence[{1, 0, 0, 1}, {14, 18, 28, 42}, 40]] (* Jean-François Alcover, Oct 26 2021 *)

Formula

G.f.: -(2*x^8+4*x^7+2*x^6+x^5+5*x^4+4*x^3+x^2+1)/(x^4+x-1).

a(n) = 2*A302510(n-2) for n >= 6.

Limit_{n-> infinity} a(n+1)/a(n) = A086106.