A060014 Sum of orders of all permutations of n letters.

1, 1, 3, 13, 67, 471, 3271, 31333, 299223, 3291487, 39020911, 543960561, 7466726983, 118551513523, 1917378505407, 32405299019941, 608246253790591, 12219834139189263, 253767339725277823, 5591088918313739017, 126036990829657056711, 2956563745611392385211

Offset: 0

Author

N. J. A. Sloane, Mar 17 2001

Keywords

• nonn
• nice
• easy

Comments

Conjecture: This sequence eventually becomes cyclic mod n for all n. - Isaac Saffold, Dec 01 2019

Examples

			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.
		

References

• D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIII.2, p. 460.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..170
• 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.

Crossrefs

Cf. A000793, A028418, A060015, A057731, A074859, A290932, A346066.

Programs

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 *)

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!))

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

Extensions

More terms from Vladeta Jovovic, Mar 18 2001

More terms from Alois P. Heinz, Feb 14 2013