|
|
A060014
|
|
Sum of orders of all permutations of n letters.
|
|
13
|
|
|
1, 1, 3, 13, 67, 471, 3271, 31333, 299223, 3291487, 39020911, 543960561, 7466726983, 118551513523, 1917378505407, 32405299019941, 608246253790591, 12219834139189263, 253767339725277823, 5591088918313739017, 126036990829657056711, 2956563745611392385211
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Conjecture: This sequence eventually becomes cyclic mod n for all n. - Isaac Saffold, Dec 01 2019
|
|
REFERENCES
|
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIII.2, p. 460.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: Sum_{n>0} (n*Sum_{i|n} (moebius(n/i)*Product_{j|i} exp(x^j/j))). - Vladeta Jovovic, Dec 29 2004; The sum over n should run to at least A000793(k) for producing the k-th entry. - Wouter Meeussen, Jun 16 2012
|
|
EXAMPLE
|
For n = 4 there is 1 permutation of order 1, 9 permutations of order 2, 8 of order 3 and 6 of order 4, for a total of 67.
|
|
MAPLE
|
b:= proc(n, g) option remember; `if`(n=0, g, add((j-1)!
*b(n-j, ilcm(g, j))*binomial(n-1, j-1), j=1..n))
end:
a:= n-> b(n, 1):
|
|
MATHEMATICA
|
CoefficientList[Series[Sum[n Fold[#1+MoebiusMu[n/#2] Apply[Times, Exp[x^#/#]&/@Divisors[#2] ]&, 0, Divisors[n]], {n, Max[Apply[LCM, Partitions[19], 1]]}], {x, 0, 19}], x] Range[0, 19]! (* Wouter Meeussen, Jun 16 2012 *)
a[ n_] := If[ n < 1, Boole[n == 0], 1 + Total @ Apply[LCM, Map[Length, First /@ PermutationCycles /@ Drop[Permutations @ Range @ n, 1], {2}], 1]]; (* Michael Somos, Aug 19 2018 *)
|
|
PROG
|
(PARI) \\ Naive method -- sum over cycles directly
cycleDecomposition(v:vec)={
my(cyc=List(), flag=#v+1, n);
while((n=vecmin(v))<#v,
my(cur=List(), i, tmp);
while(v[i++]!=n, );
while(v[i] != flag,
listput(cur, tmp=v[i]);
v[i]=flag;
i=tmp
);
if(#cur>1, listput(cyc, Vec(cur))) \\ Omit length-1 cycles
);
Vec(cyc)
};
permutationOrder(v:vec)={
lcm(apply(length, cycleDecomposition(v)))
};
a(n)=sum(i=0, n!-1, permutationOrder(numtoperm(n, i)))
(PARI)
{
my(factn = n!, part, nb, i, j, res = 0);
forpart(part = n,
nb = 1; j = 1;
for(i = 1, #part,
if (i == #part || part[i + 1] != part[i],
nb *= (i + 1 - j)! * part[i]^(i + 1 - j);
j = i + 1));
res += (factn / nb) * lcm(Vec(part)));
res;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|