cp's OEIS Frontend

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

%I A061417 #44 Jan 31 2025 17:24:05
%S A061417 1,2,4,10,28,136,726,5100,40362,363288,3628810,39921044,479001612,
%T A061417 6227066928,87178295296,1307675013928,20922789888016,355687438476444,
%U A061417 6402373705728018,121645100594641896,2432902008177690360,51090942175425331320,1124000727777607680022
%N A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.
%C A061417 If permutations are converted to (i,p(i)) permutation arrays, then this automorphism is obtained by their "SW-NE diagonal toroidal shifts" (see Matthias Engelhardt's Java program in A006841), while the Maple procedure below converts each permutation to a siteswap pattern (used in juggling), rotates it by one digit and converts the resulting new (or same) siteswap pattern back to a permutation.
%C A061417 When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.
%C A061417 The number of conjugacy classes of the symmetric group of degree n when conjugating only with the cyclic permutation group of degree n. - _Attila Egri-Nagy_, Aug 15 2014
%C A061417 Also the number of equivalence classes of permutations of {1...n} under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514). - _Gus Wiseman_, Mar 04 2019
%H A061417 T. D. Noe, <a href="/A061417/b061417.txt">Table of n, a(n) for n=1..100</a>
%H A061417 Gus Wiseman, <a href="/A061417/a061417.png">Inequivalent representatives of the a(5) = 28 permutations under rotation of vertices in the cycle decomposition</a>.
%H A061417 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A061417 a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).
%e A061417 If I have a five-element permutation like 25431, in cycle notation (1 2 5)(3 4), I mark the numbers 1-5 clockwise onto a circle and draw directed edges from 1 to 2, from 2 to 5, from 5 to 1 and a double-way edge between 3 and 4. All the 5-element permutations that produce some rotation (discarding the labels of the nodes) of that chord diagram belong to the same equivalence class with 25431. The sequence gives the count of such equivalence classes.
%p A061417 Algebraic formula: with(numtheory); SSRPCC := proc(n) local d,s; s := 0; for d in divisors(n) do s := s + phi(n/d)*((n/d)^d)*(d!); od; RETURN(s/n); end;
%p A061417 Empirically: with(group); SiteSwapRotationPermutationCycleCounts := proc(upto_n) local b,u,n,a,r; a := []; for n from 1 to upto_n do b := []; u := n!; for r from 0 to u-1 do b := [op(b),1+PermRank3R(SiteSwap2Perm1(rotateL(Perm2SiteSwap2(PermUnrank3Rfix(n,r)))))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
%p A061417 PermUnrank3Rfixaux := proc(n,r,p) local s; if(0 = n) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Rfixaux(n-1, r-(s*((n-1)!)), permul(p,[[n,n-s]]))); fi; end;
%p A061417 PermUnrank3Rfix := (n,r) -> convert(PermUnrank3Rfixaux(n,r,[]),'permlist',n);
%p A061417 SiteSwap2Perm1 := proc(s) local e,n,i,a; n := nops(s); a := []; for i from 1 to n do e := ((i+s[i]) mod n); if(0 = e) then e := n; fi; a := [op(a),e]; od; RETURN(convert(invperm(convert(a,'disjcyc')),'permlist',n)); end;
%t A061417 a[n_] := (1/n)*Sum[ EulerPhi[n/d]*(n/d)^d*d!, {d, Divisors[n]}]; Table[a[n], {n, 1, 21}] (* _Jean-François Alcover_, Oct 09 2012, from formula *)
%t A061417 Table[Length[Select[Permutations[Range[n]],#==First[Sort[NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]]]&]],{n,8}] (* _Gus Wiseman_, Mar 04 2019 *)
%o A061417 (Haskell)
%o A061417 a061417 = sum . a047917_row  -- _Reinhard Zumkeller_, Mar 19 2014
%o A061417 (GAP) List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # _Attila Egri-Nagy_, Aug 15 2014
%o A061417 (PARI) a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ _Indranil Ghosh_, Apr 10 2017
%o A061417 (Python)
%o A061417 from sympy import divisors, factorial, totient
%o A061417 def a(n):
%o A061417     return sum(totient(n//d)*(n//d)**d*factorial(d) for d in divisors(n))//n
%o A061417 print([a(n) for n in range(1, 22)]) # _Indranil Ghosh_, Apr 10 2017
%Y A061417 Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul).
%Y A061417 A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.
%Y A061417 A064636 (derangements-the same automorphism).
%Y A061417 A061417[n] = A064649[n]/n.
%Y A061417 Cf. A000031, A000939, A002995, A008965, A060223, A064640, A086675 (digraphical necklaces), A179043, A192332, A275527 (path necklaces), A323858, A323859, A323870, A324513, A324514 (aperiodic permutations).
%K A061417 nonn,easy,nice
%O A061417 1,2
%A A061417 _Antti Karttunen_, May 02 2001