A214003 Number of degree-n permutations of prime order.

0, 1, 5, 17, 69, 299, 1805, 9099, 37331, 205559, 4853529, 49841615, 789513659, 9021065871, 70737031469, 420565124399, 22959075244095, 385032305178719, 10010973102879761, 152163983393187399, 1498273284120348539, 15639918041915598815, 1296204202723400597109

Offset

1,3

Links

Stephen A. Silver, Table of n, a(n) for n = 1..451

Formula

a(n) = Sum_{p prime} A057731(n,p).

E.g.f.: exp(x)*Sum_{p in Primes} exp(x^p/p)-1. - Geoffrey Critzer, Nov 08 2015

Example

The symmetric group S_5 has 25 elements of order 2, 20 elements of order 3, and 24 elements of order 5. All other elements are of nonprime order (1, 4, or 6), so a(5) = 25 + 20 + 24 = 69.

Maple

b:= proc(n, p) option remember;
      `if`(n<p, 0, b(n-1, p)+(1+b(n-p, p))*(n-1)!/(n-p)!)
    end:
a:= n-> add(b(n, ithprime(i)), i=1..numtheory[pi](n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 16 2013
# second Maple program:
b:= proc(n, g) option remember; `if`(n=0, `if`(isprime(g), 1, 0),
      add(b(n-j, ilcm(j, g))*(n-1)!/(n-j)!, j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..23);  # Alois P. Heinz, Jan 19 2023

Mathematica

f[list_] :=Total[list]!/Apply[Times, list]/Apply[Times, Map[Length, Split[list]]!]; Table[Total[Map[f, Select[Partitions[n], PrimeQ[Apply[LCM, #]] &]]], {n, 1, 23}] (* Geoffrey Critzer, Nov 08 2015 *)

Crossrefs

Cf. A001189, A001471, A057731, A059593, A153760, A153761, A186202.

Sequence in context: A149706 A273763 A149707 * A249015 A273852 A146511

Adjacent sequences: A214000 A214001 A214002 * A214004 A214005 A214006

Keyword

nonn

Author

Stephen A. Silver, Feb 15 2013

Status

approved