login
A060181
Number of permutations in the symmetric group S_n whose order is 1 or prime.
1
1, 2, 6, 18, 70, 300, 1806, 9100, 37332, 205560, 4853530, 49841616, 789513660, 9021065872, 70737031470, 420565124400, 22959075244096, 385032305178720, 10010973102879762, 152163983393187400, 1498273284120348540, 15639918041915598816, 1296204202723400597110
OFFSET
1,2
LINKS
FORMULA
E.g.f: exp(x)-1 + exp(x)*Sum_{p prime} (exp(x^p/p)-1). - Robert Israel, Sep 18 2018
EXAMPLE
For n = 4 there is 1 permutation of order 1, 9 permutations of order 2, 8 of order 3 and no others of prime order, so a(4)=18.
MAPLE
f:= proc(n) local p, t, k;
p:= 1; t:= 1;
do
p:= nextprime(p);
if p > n then return t fi;
for k from 1 to n/p do
t:= t + n!/(p^k*(n-k*p)!*k!)
od
od
end proc:
map(f, [$1..30]); # Robert Israel, Sep 18 2018
MATHEMATICA
f[n_] := Module[{p = 1, t = 1, k}, While[True, p = NextPrime[p]; If[p > n, Return [t]]; For[k = 1, k <= n/p, k++, t = t + n!/(p^k (n - k p)! k!)]]];
f /@ Range[30] (* Jean-François Alcover, Aug 15 2020, after Robert Israel *)
CROSSREFS
Cf. A008578.
Sequence in context: A030269 A150082 A177470 * A131281 A264036 A261994
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Mar 19 2001
EXTENSIONS
Name corrected by Robert Israel, Sep 18 2018
STATUS
approved