A059838 - OEIS

%I #18 Jul 17 2022 14:19:06

%S 0,0,1,3,15,75,495,3465,29295,263655,2735775,30093525,370945575,

%T 4822292475,68916822975,1033752344625,16813959537375,285837312135375,

%U 5214921734397375,99083512953550125,2004231846526284375,42088868777051971875,934957186489800849375

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

%C 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 T. D. Noe, <a href="/A059838/b059838.txt">Table of n, a(n) for n=0..100</a>

%F E.g.f.: (1-sqrt(1-x^2))/(1-x).

%F a(2n) = (2n-1)! + (2n-1)a(2n-1), a(2n+1) = (2n+1)a(2n).

%F a(n) = n! - A000246(n). - _Victor S. Miller_

%e 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 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 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 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 (PARI) a(n)=if(n<1,0,n!-((n-1)!-a(n-1))*(n+n%2-1))

%o (GAP) List([1..9],n->Length(Filtered(SymmetricGroup(n),x->(Order(x) mod 2)=0)));

%Y Cf. A001189, A000246.

%K nonn,nice

%O 0,4

%A Avi Peretz (njk(AT)netvision.net.il), Feb 25 2001

%E Additional comments and more terms from _Victor S. Miller_, Feb 25 2001

%E Further terms and e.g.f. from _Vladeta Jovovic_, Feb 28 2001