cp's OEIS Frontend

A059838 Number of permutations in the symmetric group S_n that have even order.

%I A059838 #18 Jul 17 2022 14:19:06
%S A059838 0,0,1,3,15,75,495,3465,29295,263655,2735775,30093525,370945575,
%T A059838 4822292475,68916822975,1033752344625,16813959537375,285837312135375,
%U A059838 5214921734397375,99083512953550125,2004231846526284375,42088868777051971875,934957186489800849375
%N A059838 Number of permutations in the symmetric group S_n that have even order.
%C A059838 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])).
%H A059838 T. D. Noe, <a href="/A059838/b059838.txt">Table of n, a(n) for n=0..100</a>
%F A059838 E.g.f.: (1-sqrt(1-x^2))/(1-x).
%F A059838 a(2n) = (2n-1)! + (2n-1)a(2n-1), a(2n+1) = (2n+1)a(2n).
%F A059838 a(n) = n! - A000246(n). - _Victor S. Miller_
%e A059838 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.
%p A059838 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:
%t A059838 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 *)
%t A059838 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 *)
%o A059838 (PARI) a(n)=if(n<1,0,n!-((n-1)!-a(n-1))*(n+n%2-1))
%o A059838 (GAP) List([1..9],n->Length(Filtered(SymmetricGroup(n),x->(Order(x) mod 2)=0)));
%Y A059838 Cf. A001189, A000246.
%K A059838 nonn,nice
%O A059838 0,4
%A A059838 Avi Peretz (njk(AT)netvision.net.il), Feb 25 2001
%E A059838 Additional comments and more terms from _Victor S. Miller_, Feb 25 2001
%E A059838 Further terms and e.g.f. from _Vladeta Jovovic_, Feb 28 2001