|
| |
|
|
A062282
|
|
Number of permutations of n elements with an even number of fixed points.
|
|
6
| |
|
|
1, 0, 2, 2, 16, 64, 416, 2848, 22912, 205952, 2060032, 22659328, 271913984, 3534877696, 49488295936, 742324422656, 11877190795264, 201912243453952, 3634420382302208, 69053987263479808, 1381079745270120448
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
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...
|
|
|
FORMULA
| a(n) = sum k=0 ... [n/2] sum l=0...n-2k (-1)^l * n!/((2k)! * 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 (vladeta(AT)eunet.rs), Jan 31 2006
|
|
|
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 *)
|
|
|
CROSSREFS
| Cf. A000166, A000387, A000475.
Cf. A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.
Sequence in context: A098777 A127226 A001119 * A012319 A012520 A012323
Adjacent sequences: A062279 A062280 A062281 * A062283 A062284 A062285
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Jul 05 2001
|
| |
|
|
