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

0, 0, 1, 3, 15, 75, 495, 3465, 29295, 263655, 2735775, 30093525, 370945575, 4822292475, 68916822975, 1033752344625, 16813959537375, 285837312135375, 5214921734397375, 99083512953550125, 2004231846526284375, 42088868777051971875, 934957186489800849375

Offset: 0

Author

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

Keywords

• nonn
• nice

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])).

Examples

			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.
		

Links

• T. D. Noe, Table of n, a(n) for n=0..100

Crossrefs

Cf. A001189, A000246.

Programs

GAP

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

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

PARI

a(n)=if(n<1,0,n!-((n-1)!-a(n-1))*(n+n%2-1))

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

a(n) = n! - A000246(n). - Victor S. Miller

Extensions

Additional comments and more terms from Victor S. Miller, Feb 25 2001

Further terms and e.g.f. from Vladeta Jovovic, Feb 28 2001