A324514 -id:A324514 - cp's OEIS frontend

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

1, 2, 4, 10, 28, 136, 726, 5100, 40362, 363288, 3628810, 39921044, 479001612, 6227066928, 87178295296, 1307675013928, 20922789888016, 355687438476444, 6402373705728018, 121645100594641896, 2432902008177690360, 51090942175425331320, 1124000727777607680022

Offset: 1

Antti Karttunen, May 02 2001

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.
When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.
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
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

			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.

Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul).
A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.
A064636 (derangements-the same automorphism).
A061417[n] = A064649[n]/n.
Cf. A000031, A000939, A002995, A008965, A060223, A064640, A086675 (digraphical necklaces), A179043, A192332, A275527 (path necklaces), A323858, A323859, A323870, A324513, A324514 (aperiodic permutations).

List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014

a061417 = sum . a047917_row  -- Reinhard Zumkeller, Mar 19 2014

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;
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;
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;
PermUnrank3Rfix := (n,r) -> convert(PermUnrank3Rfixaux(n,r,[]),'permlist',n);
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;

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

a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017

from sympy import divisors, factorial, totient
def a(n):
    return sum(totient(n//d)*(n//d)**d*factorial(d) for d in divisors(n))//n
print([a(n) for n in range(1, 22)]) # Indranil Ghosh, Apr 10 2017

a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).

A086675 Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.

Original entry on oeis.org

1, 2, 10, 176, 16456, 6710912, 11453291200, 80421421917440, 2305843009750581376, 268650182136584290872320, 126765060022823052739661424640, 241677817415439249618874010960064512, 1858395433210885261795036719974526548094976

Offset: 0

Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003

Also the number of digraphical necklaces with n vertices. A digraphical necklace is defined to be a directed graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of directed graphs under rotation of the vertices. These are a kind of partially labeled digraphs. - Gus Wiseman, Mar 04 2019

			From _Gus Wiseman_, Mar 04 2019: (Start)
Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:
  {}
  {(1,1)}
  {(1,2)}
  {(1,1),(1,2)}
  {(1,1),(2,1)}
  {(1,1),(2,2)}
  {(1,2),(2,1)}
  {(1,1),(1,2),(2,1)}
  {(1,1),(1,2),(2,2)}
  {(1,1),(1,2),(2,1),(2,2)}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..57
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See p. 3.

Cf. A000031 (binary necklaces), A000939 (cycle necklaces), A008965, A060690, A061417 (permutation necklaces), A184271, A192332 (graphical necklaces), A275527 (path necklaces), A323858 (toroidal necklaces), A323870.

Cf. A324463, A324464, A324513, A324514.

Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]
(* second program *)
rotdigra[g_,m_]:=Sort[g/.k_Integer:>If[k==m,1,k+1]];
Table[Length[Select[Subsets[Tuples[Range[n],2]],#=={}||#==First[Sort[Table[Nest[rotdigra[#,n]&,#,j],{j,n}]]]&]],{n,0,4}] (* Gus Wiseman, Mar 04 2019 *)

a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n^2/d) for n > 0, a(0) = 1.

More terms from Wouter Meeussen, Jul 29 2003

a(0)=1 prepended by Gus Wiseman, Mar 04 2019

A324513 Number of aperiodic cycle necklaces with n vertices.

Original entry on oeis.org

1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

We define an aperiodic cycle necklace to be an equivalence class of (labeled, undirected) Hamiltonian cycles under rotation of the vertices such that all n of these rotations are distinct.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Inequivalent representatives of the a(6) = 7 aperiodic cycle necklaces.
Gus Wiseman, Inequivalent representatives of the a(7) = 51 aperiodic cycle necklaces.

Cf. A000740, A000939, A001037 (binary Lyndon words), A008965, A059966 (Lyndon compositions), A060223 (normal Lyndon words), A061417, A064852 (if cycle is oriented), A086675, A192332, A275527, A323866 (aperiodic toroidal arrays), A323871.

Cf. A306669, A324461, A324462, A324512, A324514.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&&UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]&]],{n,8}]

a(n)={if(n<3, n==0||n==1, (if(n%2, 0, -(n/2-1)!*2^(n/2-2)) + sumdiv(n, d, moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n^2))/2)} \\ Andrew Howroyd, Aug 19 2019

a(n) = A324512(n)/n.

a(2*n+1) = A064852(2*n+1)/2 for n > 0; a(2*n) = (A064852(2*n) - A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 16 2019

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A306669 Number of aperiodic permutation necklaces of weight n.

Original entry on oeis.org

1, 0, 1, 4, 23, 110, 719, 4992, 40302, 362492, 3628799, 39912804, 479001599, 6226974714, 87178289207, 1307673722880, 20922789887999, 355687417744992, 6402373705727999, 121645100223036700, 2432902008176115023, 51090942167993548790, 1124000727777607679999

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

A permutation is aperiodic if every rotation of {1...n} acts on the vertices of the cycle decomposition to produce a different digraph. A permutation necklace is an equivalence class of permutations 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).

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Inequivalent representatives of the a(5) = 23 aperiodic necklace permutations.

Cf. A000031, A000740, A000939, A001037, A059966, A060223, A061417, A086675, A323861, A323865, A323866, A323871.

Cf. A324461, A324512, A324513, A324514.

Table[Length[Select[Permutations[Range[n]],UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]&]]/n,{n,6}]

a(n) = (1/n)*sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019

a(n) = A324514(n)/n.

a(n) = (1/n)*Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A324512 Number of aperiodic n-gons.

Original entry on oeis.org

1, 0, 0, 0, 10, 42, 357, 2400, 20142, 180280, 1814395, 19944804, 239500794, 3113326062, 43589143560, 653834280960, 10461394943992, 177843662409312, 3201186852863991, 60822549182544440, 1216451004087794832, 25545471063559372750, 562000363888803839989

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

We define an n-gon to be aperiodic if all n rotations of its vertex set act on the edge set to give distinct n-gons. These are different from aperiodic graphs and acyclic graphs but are similar to aperiodic sequences (A000740) and aperiodic arrays (A323867).

			The a(5) = 10 aperiodic polygon edge sets:
  {{1,2},{1,3},{2,4},{3,5},{4,5}}
  {{1,2},{1,3},{2,5},{3,4},{4,5}}
  {{1,2},{1,4},{2,3},{3,5},{4,5}}
  {{1,2},{1,4},{2,5},{3,4},{3,5}}
  {{1,2},{1,5},{2,4},{3,4},{3,5}}
  {{1,3},{1,4},{2,3},{2,5},{4,5}}
  {{1,3},{1,5},{2,3},{2,4},{4,5}}
  {{1,3},{1,5},{2,4},{2,5},{3,4}}
  {{1,4},{1,5},{2,3},{2,4},{3,5}}
  {{1,4},{1,5},{2,3},{2,5},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, The a(5) = 10 aperiodic polygons.
Gus Wiseman, The a(6) = 42 aperiodic polygons.

Cf. A000740, A008965, A027375, A059966, A060223, A192332, A275527, A323860, A323867, A323869, A324461, A324462, A324513, A324514.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]&]],{n,8}]

a(n)={if(n<3, n==1, (if(n%2, 0, -n*(n/2-1)!*2^(n/2-2)) + sumdiv(n, d, moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n))/2)} \\ Andrew Howroyd, Aug 19 2019

a(n) = n * A324513(n).

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A343488 Irregular table T(n, k), n >= 0, k = 1..max(1, n), read by rows; T(n, k) is the number of permutations s of { 1..n } such that p(s) = k where p(s) is the least m > 0 such that, working in Z/nZ, s(i) + m = s(i + m) for i = 1..n.

Original entry on oeis.org

1, 1, 2, 0, 3, 0, 3, 4, 4, 0, 16, 5, 0, 0, 0, 115, 6, 12, 42, 0, 0, 660, 7, 0, 0, 0, 0, 0, 5033, 8, 24, 0, 352, 0, 0, 0, 39936, 9, 0, 153, 0, 0, 0, 0, 0, 362718, 10, 40, 0, 0, 3830, 0, 0, 0, 0, 3624920, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916789, 12, 60, 372, 1872, 0, 45636, 0, 0, 0, 0, 0, 478953648

Offset: 0

Rémy Sigrist, Apr 17 2021

We set the row for n = 0 to [1] by convention.

The number p(s) can be interpreted as the period of the permutation s.

			Table begins:
     0:     [1]
     1:     [1]
     2:     [2, 0]
     3:     [3, 0, 3]
     4:     [4, 4, 0, 16]
     5:     [5, 0, 0, 0, 115]
     6:     [6, 12, 42, 0, 0, 660]
     7:     [7, 0, 0, 0, 0, 0, 5033]
     8:     [8, 24, 0, 352, 0, 0, 0, 39936]
     9:     [9, 0, 153, 0, 0, 0, 0, 0, 362718]
    10:     [10, 40, 0, 0, 3830, 0, 0, 0, 0, 3624920]

Igor Pak, Periodic permutations and the Robinson-Schensted correspondence
Rémy Sigrist, C program for A343488
Index entries for sequences related to permutations

Cf. A000142, A324514.

C
```
See Links section.
```

T(n, 1) = max(n, 1).
T(n, n) = A324514(n).
Sum_{k = 1..max(1, n)} T(n, k) = n!.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Python

Formula

A086675 Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A324513 Number of aperiodic cycle necklaces with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A306669 Number of aperiodic permutation necklaces of weight n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A324512 Number of aperiodic n-gons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A343488 Irregular table T(n, k), n >= 0, k = 1..max(1, n), read by rows; T(n, k) is the number of permutations s of { 1..n } such that p(s) = k where p(s) is the least m > 0 such that, working in Z/nZ, s(i) + m = s(i + m) for i = 1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Formula