login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060014 Sum of orders of all permutations of n letters. 12

%I

%S 1,1,3,13,67,471,3271,31333,299223,3291487,39020911,543960561,

%T 7466726983,118551513523,1917378505407,32405299019941,608246253790591,

%U 12219834139189263,253767339725277823,5591088918313739017,126036990829657056711,2956563745611392385211

%N Sum of orders of all permutations of n letters.

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

%H Alois P. Heinz, <a href="/A060014/b060014.txt">Table of n, a(n) for n = 0..170</a>

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000058/">The order of a permutation</a>

%H Joshua Harrington, Lenny Jones, and Alicia Lamarche, <a href="http://dx.doi.org/10.1155/2014/835125">Characterizing Finite Groups Using the Sum of the Orders of the Elements</a>, International Journal of Combinatorics, Volume 2014, Article ID 835125, 8 pages

%F 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

%F a(n) = sum_{k>=1} k* A057731(n,k). - _R. J. Mathar_, Aug 31 2017

%e 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.

%p b:= proc(n, g) option remember; `if`(n=0, g, add((j-1)!

%p *b(n-j, ilcm(g, j))*binomial(n-1, j-1), j=1..n))

%p end:

%p a:= n-> b(n, 1):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jul 11 2017

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

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

%o (PARI) \\ Naive method -- sum over cycles directly

%o cycleDecomposition(v:vec)={

%o my(cyc=List(), flag=#v+1, n);

%o while((n=vecmin(v))<#v,

%o my(cur=List(), i, tmp);

%o while(v[i++]!=n,);

%o while(v[i] != flag,

%o listput(cur, tmp=v[i]);

%o v[i]=flag;

%o i=tmp

%o );

%o if(#cur>1, listput(cyc, Vec(cur))) \\ Omit length-1 cycles

%o );

%o Vec(cyc)

%o };

%o permutationOrder(v:vec)={

%o lcm(apply(length, cycleDecomposition(v)))

%o };

%o a(n)=sum(i=0,n!-1,permutationOrder(numtoperm(n,i)))

%o \\ _Charles R Greathouse IV_, Nov 06 2014

%o (PARI)

%o A060014(n) =

%o {

%o my(factn = n!, part, nb, i, j, res = 0);

%o forpart(part = n,

%o nb = 1; j = 1;

%o for(i = 1, #part,

%o if (i == #part || part[i + 1] != part[i],

%o nb *= (i + 1 - j)! * part[i]^(i + 1 - j);

%o j = i + 1));

%o res += (factn / nb) * lcm(Vec(part)));

%o res;

%o } \\ _Jerome Raulin_, Jul 11 2017 (much faster, O(A000041(n)) vs O(n!))

%Y Cf. A000793, A028418, A060015, A057731, A074859, A290932.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_, Mar 17 2001

%E More terms from _Vladeta Jovovic_, Mar 18 2001

%E More terms from _Alois P. Heinz_, Feb 14 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 07:53 EDT 2019. Contains 322327 sequences. (Running on oeis4.)