A074351 Number of elements of S_n having order n.

1, 1, 2, 6, 24, 240, 720, 5040, 40320, 514080, 3628800, 80166240, 479001600, 6797831040, 93774320640, 1307674368000, 20922789888000, 523845011289600, 6402373705728000, 153101632051630080, 2471368711740364800, 51182316789956352000, 1124000727777607680000

Offset

1,3

Comments

If n is a prime power then a(n) = (n-1)!. - Vladeta Jovovic, Sep 29 2002

Links

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from T. D. Noe)

J. Kuzmanovich and A. Pavlichenkov, Finite groups of matrices whose entries are integers, Amer. Math. Monthly, 109 (2002), 173-186.

Formula

n!/(a_1!*a_2!*...*a_d!*k_1^a_1*k_2^a_2*...*k_d^a_d) is the number of elements of S_n having order n that are permutations with distinct cycle-lengths k_1, ..., k_d having multiplicities a_1, ..., a_d, where lcm(k_1, ..., k_d)=n. Summing over all permutation types gives the total.

a(n) = n!*coefficient of x^n in expansion of Sum_{i divides n} mu(n/i)*exp(Sum_{j divides i} x^j/j). - Vladeta Jovovic, Sep 29 2002

Example

a(10) = 514080 because {10}, {5, 2, 2, 1} and {5, 2, 1, 1, 1} are the unique multisets of cycle lengths summing to 10 whose lcm is 10 and 10!/(1!*10^1) + 10!/(1!*2!*1!*5^1*2^2*1^1) + 10!/(1!*1!*3!*5^1*2^1*1^3) = 514080.

Mathematica

a[n_] := SeriesCoefficient[ Series[ Sum[ MoebiusMu[n/i]*Exp[Sum[x^j/j, {j, Divisors[i]}]], {i, Divisors[n]}], {x, 0, n}], n]*n!; Table[a[n], {n, 1, 21}] (* Jean-François Alcover, May 21 2012, after Vladeta Jovovic *)

Prog

(PARI) a(n)={n!*polcoeff(sumdiv(n, i, moebius(n/i)*exp(sumdiv(i, j, x^j/j) + O(x*x^n))), n)} \\ Andrew Howroyd, Jul 02 2018

Crossrefs

Cf. A001189, A074859, A290961 (the same for endofunctions).

Main diagonal of A057731.

Sequence in context: A355284 A034874 A052699 * A352060 A346121 A052597

Adjacent sequences: A074348 A074349 A074350 * A074352 A074353 A074354

Keyword

nice,easy,nonn

Author

K Murray Peebles (m.peebles(AT)sms.ed.ac.uk), Sep 26 2002

Status

approved