login
A162969
Number of permutations of {1,2,...,n} in which the fixed points and the non-fixed points alternate.
2
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
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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jul 19 2009
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jul 21 2017
STATUS
approved