A162969 Number of permutations of {1,2,...,n} in which the fixed points and the non-fixed points alternate.

1, 1, 0, 1, 2, 3, 4, 11, 18, 53, 88, 309, 530, 2119, 3708, 16687, 29666, 148329, 266992, 1468457, 2669922, 16019531, 29369140, 190899411, 352429682, 2467007773, 4581585864, 34361893981, 64142202098, 513137616783, 962133031468, 8178130767479, 15394128503490

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..899

Formula

a(2n-1) = d(n-1) + d(n), a(2n) = 2*d(n) for n>0, where d(j) = A000166(j) is a derangement number.

D-finite with recurrence 2*a(n) +2*a(n-1) +(-n+1)*a(n-2) +(-n+4)*a(n-3) +(-n+1)*a(n-4) +(-n+4)*a(n-5)=0. - R. J. Mathar, Jul 22 2022

a(n) mod 2 = n mod 2 = A000035(n) for n>=1. - Alois P. Heinz, Apr 18 2024

Example

a(5)=3 because we have 14325, 32541, and 52143;
a(6)=4 because we have 143652, 163254, 325416, and 521436.

Maple

d := proc(n) if n = 0 then 1 else n*d(n-1)+(-1)^n end if end proc: a := proc(n) if n=0 then 1 elif `mod`(n, 2) = 0 then 2*d((1/2)*n) else d((1/2)*n-1/2)+d((1/2)*n+1/2) end if end proc: seq(a(n), n = 0 .. 36);

Mathematica

d = Subfactorial;
a[n_] := If[n==0, 1, If[EvenQ[n], 2 d[n/2], d[(n-1)/2] + d[(n+1)/2]]];
a /@ Range[0, 32] (* Jean-François Alcover, Nov 28 2020 *)

Crossrefs

Cf. A000035, A000166, A372102.

Sequence in context: A002098 A301318 A297180 * A104109 A066347 A367807

Adjacent sequences: A162966 A162967 A162968 * A162970 A162971 A162972

Keyword

nonn,easy,changed

Author

Emeric Deutsch, Jul 19 2009

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 21 2017

Status

approved