[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a086675 -id:a086675
Displaying 1-7 of 7 results found. page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces. +10
16
1, 2, 4, 10, 28, 136, 726, 5100, 40362, 363288, 3628810, 39921044, 479001612, 6227066928, 87178295296, 1307675013928, 20922789888016, 355687438476444, 6402373705728018, 121645100594641896, 2432902008177690360, 51090942175425331320, 1124000727777607680022 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
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
LINKS
T. D. Noe, Table of n, a(n) for n=1..100
Gus Wiseman, Inequivalent representatives of the a(5) = 28 permutations under rotation of vertices in the cycle decomposition.
Index entries for sequences related to necklaces
FORMULA
a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).
EXAMPLE
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.
MAPLE
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;
MATHEMATICA
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 *)
PROG
(Haskell)
a061417 = sum . a047917_row -- Reinhard Zumkeller, Mar 19 2014
(GAP) List([1..10], n->Size( OrbitsDomain( CyclicGroup(I sPermGroup, n), SymmetricGroup( IsPermGroup, n), \^))); # Attila Egri-Nagy, Aug 15 2014
(PARI) a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017
(Python)
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
CROSSREFS
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).
KEYWORD
nonn,easy,nice
AUTHOR
Antti Karttunen, May 02 2001
STATUS
approved
A192332 For n >= 3, draw a regular n-sided polygon and its n(n-3)/2 diagonals, so there are n(n-1)/2 lines; a(n) is the number of ways to choose a subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=1, a(2)=2 by convention. +10
16
1, 2, 4, 22, 208, 5560, 299600, 33562696, 7635498336, 3518440564544, 3275345183542208, 6148914696963883712, 23248573454127484129024, 176848577040808821410837120, 2704321280486889389864215362560, 83076749736557243209409446411255936, 5124252113632955685095523500148980125696, 634332307869315502692705867068871886072665600 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
Suggested by A192314.
Also the number of graphical necklaces with n vertices. We define a graphical necklace to be a simple graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of simple graphs under rotation of the vertices. These are a kind of partially labeled graphs. - Gus Wiseman, Mar 04 2019
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..80
Gus Wiseman, Inequivalent representatives of the a(5) = 22 graphical necklaces.
Gus Wiseman, Inequivalent representatives of the a(5) = 208 graphical necklaces.
FORMULA
a(n) = (1/n)*(Sum_{d|n, d odd} phi(d)*2^(n*(n-1)/(2*d)) + Sum_{d|n, d even} phi(d)*2^(n^2/(2*d))).
EXAMPLE
From Gus Wiseman, Mar 04 2019: (Start)
Inequivalent representatives of the a(1) = 1 through a(4) = 22 graphical necklace edge-sets:
{} {} {} {}
{{12}} {{12}} {{12}}
{{12}{13}} {{13}}
{{12}{13}{23}} {{12}{13}}
{{12}{14}}
{{12}{24}}
{{12}{34}}
{{13}{24}}
{{12}{13}{14}}
{{12}{13}{23}}
{{12}{13}{24}}
{{12}{13}{34}}
{{12}{14}{23}}
{{12}{24}{34}}
{{12}{13}{14}{23}}
{{12}{13}{14}{24}}
{{12}{13}{14}{34}}
{{12}{13}{24}{34}}
{{12}{14}{23}{34}}
{{12}{13}{14}{23}{24}}
{{12}{13}{14}{23}{34}}
{{12}{13}{14}{23}{24}{34}}
(End)
MAPLE
with(numtheory);
f:=proc(n) local t0, t1, d; t0:=0; t1:=divisors(n);
for d in t1 do
if d mod 2 = 0 then t0:=t0+phi(d)*2^(n^2/(2*d))
else t0:=t0+phi(d)*2^(n*(n-1)/(2*d)); fi; od; t0/n; end;
[seq(f(n), n=1..30)];
MATHEMATICA
Table[ 1/n* Plus @@ Map[Function[d, EulerPhi[d]*2^((n*(n - Mod[d, 2])/2)/d)], Divisors[n]], {n, 1, 20}] (* Olivier Gérard, Aug 27 2011 *)
rotgra[g_, m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m, 1, k+1])];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], #=={}||#==First[Sort[Table[Nest[rotgra[#, n]&, #, j], {j, n}]]]&]], {n, 0, 5}] (* Gus Wiseman, Mar 04 2019 *)
PROG
(PARI) a(n) = sumdiv(n, d, if (d%2, eulerphi(d)*2^(n*(n-1)/(2*d)), eulerphi(d)*2^(n^2/(2*d))))/n; \\ Michel Marcus, Mar 08 2019
CROSSREFS
Cf. A192314, A191563 (orbits under dihedral group).
Cf. A000031, A000939 (cycle necklaces), A008965, A059966, A060223, A061417, A086675 (digraph version), A184271, A275527, A323858, A324461, A324463, A324464.
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jun 28 2011
STATUS
approved
A324513 Number of aperiodic cycle necklaces with n vertices. +10
8
1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
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.
LINKS
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.
FORMULA
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
MATHEMATICA
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}]
PROG
(PARI) 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
CROSSREFS
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.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2019
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019
STATUS
approved
A324514 Number of aperiodic permutations of {1..n}. +10
7
1, 0, 3, 16, 115, 660, 5033, 39936, 362718, 3624920, 39916789, 478953648, 6227020787, 87177645996, 1307674338105, 20922779566080, 355687428095983, 6402373519409856, 121645100408831981, 2432902004460734000, 51090942171698415483, 1124000727695858073380 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A permutation is defined to be aperiodic if every cyclic rotation of {1..n} acts on the cycle decomposition to produce a different digraph.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Cycle decompositions of the a(4) = 16 aperiodic permutations.
FORMULA
a(n) = A306669(n) * n.
a(n) = Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019
EXAMPLE
The a(4) = 16 aperiodic permutations:
(1243) (1324) (1342) (1423)
(2134) (2314) (2413) (2431)
(3124) (3142) (3241) (3421)
(4132) (4213) (4231) (4312)
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n, 1, k+1]]&, #, n-1]&]], {n, 6}]
PROG
(PARI) a(n) = sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019
CROSSREFS
Cf. A000740, A000939, A027375, A061417, A079128, A086675, A192332, A323860, A323867, A323869.
Cf. A306669, A324461, A324462, A324512, A324513, A324514.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2019
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019
STATUS
approved
A306669 Number of aperiodic permutation necklaces of weight n. +10
5
1, 0, 1, 4, 23, 110, 719, 4992, 40302, 362492, 3628799, 39912804, 479001599, 6226974714, 87178289207, 1307673722880, 20922789887999, 355687417744992, 6402373705727999, 121645100223036700, 2432902008176115023, 51090942167993548790, 1124000727777607679999 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
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).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Inequivalent representatives of the a(5) = 23 aperiodic necklace permutations.
FORMULA
a(n) = A324514(n)/n.
a(n) = (1/n)*Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n, 1, k+1]]&, #, n-1]&]]/n, {n, 6}]
PROG
(PARI) a(n) = (1/n)*sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019
CROSSREFS
Cf. A000031, A000740, A000939, A001037, A059966, A060223, A061417, A086675, A323861, A323865, A323866, A323871.
Cf. A324461, A324512, A324513, A324514.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2019
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019
STATUS
approved
A306715 Number of graphical necklaces with n vertices and distinct rotations. +10
2
1, 0, 2, 12, 204, 5372, 299592, 33546240, 7635496960, 3518433853392, 3275345183542176, 6148914685509544960, 23248573454127484128960, 176848577040728399988915648, 2704321280486889389857342715776, 83076749736557240903566436660674560 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A simple graph with n vertices has distinct rotations if all n rotations of its vertex set act on the edge set to give distinct graphs. A graphical necklace is a simple graph that is minimal among all n rotations of the vertices.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..50
Gus Wiseman, Inequivalent representatives of the a(4) = 12 graphical necklaces with distinct rotations.
FORMULA
a(n > 0) = A324461(n)/n.
a(n) = (1/n)*Sum_{d|n} mu(d)*2^(n*(n/d-1)/2 + n*floor(d/2)/d) for n > 0. - Andrew Howroyd, Aug 15 2019
MATHEMATICA
rotgra[g_, m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m, 1, k+1])];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], With[{rots=Table[Nest[rotgra[#, n]&, #, j], {j, n}]}, UnsameQ@@rots&&#==First[Sort[rots]]]&]], {n, 5}]
PROG
(PARI) a(n)={if(n==0, 1, sumdiv(n, d, moebius(d)*2^(n*(n/d-1)/2 + n*(d\2)/d))/n)} \\ Andrew Howroyd, Aug 15 2019
CROSSREFS
Cf. A000088, A001037, A006125, A059966, A060223, A086675, A192332 (graphical necklaces), A306669, A323861, A323865, A323866, A323871, A324461 (distinct rotations), A324513.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 05 2019
EXTENSIONS
Terms a(7) and beyond from Andrew Howroyd, Aug 15 2019
STATUS
approved
A086683 Number of n X n {-1,0,1} matrices modulo cyclic permutations of the rows. +10
1
1, 3, 45, 6579, 10763361, 169457722083, 25015772614247325, 34185618461516789943315, 429210477536564292209765507601, 49269609804781974438694405096704997875, 51537752073201133103646184766360896456864366605, 490093718158481239203594498957165010835856989328505008243 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..40
FORMULA
a(n) = (1/n)*Sum_{ d divides n } phi(d)*3^(n^2/d) for n > 0.
PROG
(PARI) a(n) = if(n<1, n==0, sumdiv(n, d, eulerphi(d)*3^(n^2/d))/n);
CROSSREFS
Cf. A086675, A060336.
KEYWORD
nonn
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
EXTENSIONS
a(0)=1 prepended and terms a(7) and beyond from Andrew Howroyd, Jul 08 2018
STATUS
approved
page 1

Search completed in 0.012 seconds

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 29 21:34 EDT 2024. Contains 375518 sequences. (Running on oeis4.)