A062282 Number of permutations of n elements with an even number of fixed points.

1, 0, 2, 2, 16, 64, 416, 2848, 22912, 205952, 2060032, 22659328, 271913984, 3534877696, 49488295936, 742324422656, 11877190795264, 201912243453952, 3634420382302208, 69053987263479808, 1381079745270120448, 29002674650671480832, 638058842314774675456

Offset: 0

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001

Keywords

• nonn

Comments

Let d(n) be the number of derangements of n elements (sequence A000166) then a(n) has the recursion: a(n) = d(n) + C(n,2)*d(n-2) + C(n,4)*d(n-4) + C(n,6)*d(n-6)... = A000166(n) + A000387(n) + A000475(n) + C(n,6)*d(n-6)... The E.g.f. for a(n) is: cosh(x) * exp(-x)/(1-x) and the asymptotic expression for a(n) is: a(n) ~ n! * (1 + 1/e^2)/2 i.e., as n goes to infinity the fraction of permutations that has an even number of fixed points is about (1 + 1/e^2)/2 = 0.567667...

Links

• G. C. Greubel, Table of n, a(n) for n = 0..445

Crossrefs

Cf. A000166, A000387, A000475.

Cf. A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

Programs

Mathematica

nn = 20; d = Exp[-x]/(1 - x); Range[0, nn]! CoefficientList[Series[Cosh[x] d, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 14 2012 *)
Table[Sum[Sum[(-1)^j * n!/(j!*(2*k)!), {j, 0, n - 2*k}], {k, 0, Floor[n/2]}], {n,0,50}] (* G. C. Greubel, Aug 21 2017 *)

PARI

for(n=0,50, print1(sum(k=0,n\2, sum(j=0,n-2*k, (-1)^j*n!/(j!*(2*k)!))), ", ")) \\ G. C. Greubel, Aug 21 2017

Formula

a(n) = Sum_{k=0..[n/2]} Sum_{l=0..(n-2*k)} (-1)^l * n!/((2*k)! * l!).

More generally, e.g.f. for number of degree-n permutations with an even number of k-cycles is cosh(x^k/k)*exp(-x^k/k)/(1-x). - Vladeta Jovovic, Jan 31 2006

E.g.f.: 1/(1-x)/(x*E(0)+1), where E(k) = 1 - x^2/( x^2 + (2*k+1)*(2*k+3)/E(k+1) ); (continued fraction ). - Sergei N. Gladkovskii, Dec 29 2013

Conjecture: a(n) = Sum_{k=0..n} A008290(n, k)*A059841(k). - John Keith, Jun 30 2020

Extensions

More terms from Vladeta Jovovic, Jul 05 2001