A268306 The number of even permutations p of 1,2,...,n such that -1<=p(i)-i<=2 for i=1,2,...,n.

1, 1, 2, 4, 7, 12, 22, 41, 75, 137, 252, 464, 853, 1568, 2884, 5305, 9757, 17945, 33006, 60708, 111659, 205372, 377738, 694769, 1277879, 2350385, 4323032, 7951296, 14624713, 26899040, 49475048, 90998801, 167372889, 307846737, 566218426

Offset: 1

Author

Dmitry Efimov, Jan 31 2016

Keywords

• easy
• nonn

Examples

			There exist two even permutations p of 1,2,3 such that -1<=p(i)-i<=2 for i=1,2,3: (123) and (312), therefore a(3)=2.
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-1,0,-1).

Crossrefs

Cf. A133872, A000073, A001710, A003221.

Programs

Mathematica

CoefficientList[Series[(1 - x + x^2 - x^3 - x^5)/((1 - x) (1 + x^2) (1 - x - x^2 - x^3)), {x, 0, 34}], x] (* Michael De Vlieger, Feb 01 2016 *)

Maxima

t1:0$ t2:0$ t3:1$  for i:1 thru 100 do (a:1/2+sin((2*i+1)*%pi/4)/sqrt(2),
t:t1+t2+t3, t1:t2, t2:t3, t3:t, e:(t+a)/2, print(e));

PARI

Vec(x*(1-x+x^2-x^3-x^5)/((1-x)*(1+x^2)*(1-x-x^2-x^3)) + O(x^50)) \\ Colin Barker, Jan 31 2016

Formula

a(n) = A133872(n)/2 + A000073(n+2)/2.

G.f.: x*(1-x+x^2-x^3-x^5) / ((1-x)*(1+x^2)*(1-x-x^2-x^3)). - Colin Barker, Jan 31 2016