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,4

Links

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

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

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 *)

Prog

(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

Crossrefs

Cf. A062282.

Sequence in context: A123106 A123288 A192200 * A349859 A270399 A269998

Adjacent sequences: A063080 A063081 A063082 * A063084 A063085 A063086

Keyword

nonn

Author

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

Extensions

More terms from Wouter Meeussen, Aug 09 2001

Status

approved