|
|
A059838
|
|
Number of permutations in the symmetric group S_n that have even order.
|
|
4
|
|
|
0, 0, 1, 3, 15, 75, 495, 3465, 29295, 263655, 2735775, 30093525, 370945575, 4822292475, 68916822975, 1033752344625, 16813959537375, 285837312135375, 5214921734397375, 99083512953550125, 2004231846526284375, 42088868777051971875, 934957186489800849375
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
From Bob Beals: Let P[n] = probability that a random permutation in S_n has odd order. Then P[n] = sum_k P[random perm in S_n has odd order | n is in a cycle of length k] * P[n is in a cycle of length k]. Now P[n is in a cycle of length k] = 1/n; P[random perm in S_n has odd order | k is even] = 0; P[random perm in S_n has odd order | k is odd] = P[ random perm in S_{n-k} has odd order]. So P[n] = (1/n) * sum_{k odd} P[n-k] = (1/n) P[n-1] + (1/n) sum_{k odd and >=3} P[n-k] = (1/n)*P[n-1] + ((n-2)/n)*P[n-2] and P[1] = 1, P[2] = 1/2. The solution is: P[n] = (1 - 1/2) (1 - 1/4) ... (1-1/(2*[n/2])).
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: (1-sqrt(1-x^2))/(1-x).
a(2n) = (2n-1)! + (2n-1)a(2n-1), a(2n+1) = (2n+1)a(2n).
|
|
EXAMPLE
|
A permutation in S_4 has even order iff it is a transposition, a product of two disjoint transpositions or a 4 cycle so a(4) = C(4,2)+ C(4,2)/2 + 3! = 15.
|
|
MAPLE
|
s := series((1-sqrt(1-x^2))/(1-x), x, 21): for i from 0 to 20 do printf(`%d, `, i!*coeff(s, x, i)) od:
|
|
MATHEMATICA
|
a[n_] := a[n] = n! - ((n-1)! - a[n-1]) * (n+Mod[n, 2]-1); a[0] = 0; Table[a[n], {n, 0, 20}](* Jean-François Alcover, Nov 21 2011, after Pari *)
With[{nn=20}, CoefficientList[Series[(1-Sqrt[1-x^2])/(1-x), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Aug 05 2015 *)
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, n!-((n-1)!-a(n-1))*(n+n%2-1))
(GAP) List([1..9], n->Length(Filtered(SymmetricGroup(n), x->(Order(x) mod 2)=0)));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Avi Peretz (njk(AT)netvision.net.il), Feb 25 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|