0,4

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

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

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

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.

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:

(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)));

Cf. A001189, A000246.

Sequence in context: A005053 A136778 A000266 this_sequence A079164 A047015 A037759

Adjacent sequences: A059835 A059836 A059837 this_sequence A059839 A059840 A059841

nonn,nice

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

Additional comments and more terms from Victor S. Miller, victor(AT)idaccr.org, Feb 25, 2001. Further terms and e.g.f. from Vladeta Jovovic (vladeta(AT)Eunet.yu), Feb 28 2001.