VOOZH about

URL: https://oeis.org/A060014

⇱ A060014 - OEIS

login
A060014
Sum of orders of all permutations of n letters.
14
1, 1, 3, 13, 67, 471, 3271, 31333, 299223, 3291487, 39020911, 543960561, 7466726983, 118551513523, 1917378505407, 32405299019941, 608246253790591, 12219834139189263, 253767339725277823, 5591088918313739017, 126036990829657056711, 2956563745611392385211
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
FindStat - Combinatorial Statistic Finder, The order of a permutation
Joshua Harrington, Lenny Jones, and Alicia Lamarche, Characterizing Finite Groups Using the Sum of the Orders of the Elements, International Journal of Combinatorics, Volume 2014, Article ID 835125, 8 pages.
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
a(n) = Sum_{k>=1} k* A057731(n,k). - R. J. Mathar, Aug 31 2017
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):
seq(a(n), n=0..30); # Alois P. Heinz, Jul 11 2017
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)))
\\ Charles R Greathouse IV, Nov 06 2014
(PARI)
A060014(n) =
{
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;
} \\ Jerome Raulin, Jul 11 2017 (much faster, O(A000041(n)) vs O(n!))
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, Mar 17 2001
EXTENSIONS
More terms from Vladeta Jovovic, Mar 18 2001
More terms from Alois P. Heinz, Feb 14 2013
STATUS
approved