A063083 Number of permutations of n elements with an odd number of fixed points.

0, 1, 0, 4, 8, 56, 304, 2192, 17408, 156928, 1568768, 17257472, 207087616, 2692143104, 37689995264, 565349945344, 9045599092736, 153775184642048, 2767953323425792, 52591113145352192, 1051822262906519552, 22088267521037959168, 485941885462833004544

Offset: 0

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 05 2001

Keywords

• nonn

Links

• Harry J. Smith, Table of n, a(n) for n=0..100

Crossrefs

Cf. A062282.

Programs

Mathematica

nn = 20; d = Exp[-x]/(1 - x); Range[0, nn]! CoefficientList[Series[Sinh[x]  d, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 14 2012 *)
a[n_] := -n!/2 Sum[(-2)^i/i!, {i, 1, n}]
Table[a[n], {n, 0, 20}] (* Gerry Martens , May 06 2016 *)

PARI

{ for (n=0, 100, if (n, a=n*a + (-2)^(n-1), a=0); write("b063083.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 17 2009

Formula

E.g.f.: sinh(x) * exp(-x)/(1-x). Asymptotic expression: a(n) ~ n! * (1 - 1/e^2)/2 i.e. as n goes to infinity the fraction for permutations that has an odd number of fixed points is about (1 - 1/e^2)/2 = 0.432332...

a(n) = n! - A062282(n) = n! - sum k=0 ... [n/2] sum l=0...n-2k (-1)^l * n!/((2k)! * l!)

Recurrence: a(n) = n*a(n-1)+(-2)^(n-1). - Vladeta Jovovic, Apr 11 2003

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

a(n) = (Gamma(n+1) - Gamma(n+1,-2)*exp(-2))/2, where Gamma(a,x) is the incomplete gamma function. - Ilya Gutkovskiy, May 06 2016

Extensions

More terms from Wouter Meeussen, Aug 09 2001