A323858 -id:A323858 - cp's OEIS frontend

A184271 Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal binary arrays (n >= 1, k >= 1).

2, 3, 3, 4, 7, 4, 6, 14, 14, 6, 8, 40, 64, 40, 8, 14, 108, 352, 352, 108, 14, 20, 362, 2192, 4156, 2192, 362, 20, 36, 1182, 14624, 52488, 52488, 14624, 1182, 36, 60, 4150, 99880, 699600, 1342208, 699600, 99880, 4150, 60, 108, 14602, 699252, 9587580, 35792568

Offset: 1

R. H. Hardin, Jan 10 2011

This is a 2-dimensional generalization of binary necklaces (A000031). A toroidal array or necklace can be defined either as an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns, or as a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns. - Gus Wiseman, Feb 04 2019

			      1     2        3           4            5             6              7
----------------------------------------------------------------------------
1:    2     3        4           6            8            14             20
2:    3     7       14          40          108           362           1182
3:    4    14       64         352         2192         14624          99880
4:    6    40      352        4156        52488        699600        9587580
5:    8   108     2192       52488      1342208      35792568      981706832
6:   14   362    14624      699600     35792568    1908897152   104715443852
7:   20  1182    99880     9587580    981706832  104715443852 11488774559744
8:   36  4150   699252   134223976  27487816992 5864063066500
9:   60 14602  4971184  1908881900 781874936816
10: 108 52588 35792568 27487869472
From _Gus Wiseman_, Feb 04 2019: (Start)
Inequivalent representatives of the T(2,3) = 14 toroidal necklaces:
  [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1]
  [0 0 0] [0 0 1] [0 1 1] [1 1 1] [0 0 1] [0 1 0] [0 1 1]
.
  [0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]
  [1 0 1] [1 1 0] [1 1 1] [0 1 1] [1 0 1] [1 1 1] [1 1 1]
(End)

Alois P. Heinz, Antidiagonals n = 1..100, flattened (first 95 terms from R. H. Hardin)
S. N. Ethier, Counting toroidal binary arrays, arXiv preprint arXiv:1301.2352, 2013 and J. Int. Seq. 16 (2013) #13.4.7 .
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023.
Wikipedia, Pólya enumeration theorem

Columns 1-8 are A000031, A184264, A184265, A184266, A184267, A184268, A184269, A184270.
Main diagonal is A179043.
Cf. A001037 (binary Lyndon words), A008965, A323858, A323859 (binary toroidal necklaces of size n), A323861 (aperiodic version), A323865, A323870 (normal toroidal necklaces), A323872.

a[n_, k_] := Sum[If[Mod[n, c] == 0, Sum[If[Mod[k, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n k/LCM[c, d]), 0], {d, 1, k}], 0], {c, 1, n}]/(n k)
(* second program *)
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[Length[Select[Partition[#,n-k]&/@Tuples[{0,1},(n-k)*k],neckmatQ]],{n,8},{k,n-1}] (* Gus Wiseman, Feb 04 2019 *)

T(n,k) = (1/(nk))*Sum_{ c divides n } Sum_{ d divides k } phi(c)*phi(d)*2^(nk/lcm(c,d)), where phi is A000010 and lcm stands for least common multiple. - Stewart N. Ethier, Aug 24 2012

A179043 Number of n X n checkered tori.

Original entry on oeis.org

1, 2, 7, 64, 4156, 1342208, 1908897152, 11488774559744, 288230376353050816, 29850020237398264483840, 12676506002282327791964489728, 21970710674130840874443091905462272, 154866286100907105149651981766316633972736

Offset: 0

Rouben Rostamian (rostamian(AT)umbc.edu), Jun 25 2010

nonn

Consider an n X n checkerboard whose tiles are assigned colors 0 and 1, at random. There are 2^(n^2) such checkerboards. We identify the opposite edges of each checkerboard, thus making it into a (topological) torus. There are a(n) such (distinct) tori. It is possible to show that a(n) >= 2^(n^2)/n^2 for all n.
Main diagonal of A184271.
Main diagonal of Table 3: The number a(m, n) of toroidal m X n binary arrays, allowing rotation of the rows and/or the columns but not reflection, for m, n = 1, 2, ..., 8, at page 5 of Ethier. - Jonathan Vos Post, Jan 14 2013
This is a 2-dimensional generalization of binary necklaces (A000031). - Gus Wiseman, Feb 04 2019

			From _Gus Wiseman_, Feb 04 2019: (Start)
Inequivalent representatives of the a(2) = 7 checkered tori:
  [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
  [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..57
S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352v1 [math.CO], Jan 10, 2013 and J. Int. Seq. 16 (2013) #13.4.7 .
S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015 and J. Int. Seq. 18 (2015) # 15.8.3.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Peter Kagey and William Keehn, Counting Tilings of the n X m Grid, Cylinder, and Torus, J. Int. Seq. (2024) Vol. 27, Art. No. 24.6.1. See p. 2.
Wikipedia, Pólya enumeration theorem

Cf. A184271 (n X k toroidal binary arrays).
Cf. A000031, A001037, A008965.
Cf. A323858, A323859, A323861, A323863, A323865, A323870, A323872.

a[n_] := Sum[If[Mod[n, c] == 0, Sum[If[Mod[n, d] == 0, EulerPhi[c] EulerPhi[d] 2^(n^2/LCM[c, d]), 0], {d, 1, n}], 0], {c, 1, n}]/n ^2

a(n) = (1/n^2)*Sum_{ c divides n } Sum_{ d divides n } phi(c)*phi(d)*2^(n^2/lcm(c,d)), where phi is A000010 and lcm stands for least common multiple. - Stewart N. Ethier, Aug 24 2012

Terms a(6) and a(7) from A184271
a(8)-a(12) from Stewart N. Ethier, Aug 24 2012
a(0)=1 prepended by Alois P. Heinz, Aug 20 2017

A000939 Number of inequivalent n-gons.

Original entry on oeis.org

1, 1, 1, 2, 4, 14, 54, 332, 2246, 18264, 164950, 1664354, 18423144, 222406776, 2905943328, 40865005494, 615376173184, 9880209206458, 168483518571798, 3041127561315224, 57926238289970076, 1161157777643184900, 24434798429947993054, 538583682082245127336

Offset: 1

N. J. A. Sloane

Here two n-gons are said to be equivalent if they differ in starting point, orientation, or by a rotation (but not by a reflection - for that see A000940).

Number of cycle necklaces on n vertices, defined as equivalence classes of (labeled, undirected) Hamiltonian cycles under rotation of the vertices. The path version is A275527. - Gus Wiseman, Mar 02 2019

			Possibilities for n-gons without distinguished vertex can be encoded as permutation classes of vertices, two permutations being equivalent if they can be obtained from each other by circular rotation, translation mod n or complement to n+1.
n=3: 123.
n=4: 1234, 1243.
n=5: 12345, 12354, 12453, 13524.
n=6: 123456, 123465, 123564, 123645, 123654, 124365, 124635, 124653, 125364, 125463, 125634, 126435, 126453, 135264.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Georg Fischer, Table of n, a(n) for n = 1..450 (first 100 terms by T. D. Noe)
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Wikipedia, Hamiltonian path.
Wikipedia, Polygon.
Gus Wiseman, Inequivalent representatives of the a(6) = 14 cycle necklaces.
Gus Wiseman, Inequivalent representatives of the a(7) = 54 n-gons.

Cf. A000940. Bisections give A094154, A094155.
For star polygons see A231091.
Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.

with(numtheory):
# for n odd:
Ed:= proc(n) local t1, d; t1:=0; for d from 1 to n do
       if n mod d = 0 then t1:= t1+phi(n/d)^2*d!*(n/d)^d fi od:
       t1/(2*n^2)
     end:
# for n even:
Ee:= proc(n) local t1, d; t1:= 2^(n/2)*(n/2)*(n/2)!; for d
       from 1 to n do if n mod d = 0 then t1:= t1+
       phi(n/d)^2*d!*(n/d)^d; fi od: t1/(2*n^2)
     end:
A000939:= n-> if n mod 2 = 0 then ceil(Ee(n)) else ceil(Ed(n)); fi:
seq(A000939(n), n=1..25);

a[n_] := (t = If[OddQ[n], 0, 2^(n/2)*(n/2)*(n/2)!]; Do[If[Mod[n, d]==0, t = t+EulerPhi[n/d]^2*d!*(n/d)^d], {d, 1, n}]; t/(2*n^2)); a[1] := 1; a[2] := 1; Print[a /@ Range[1, 450]] (* Jean-François Alcover, May 19 2011, after Maple prog. *)
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}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

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

For formula see Maple lines.
a(2*n + 1) =  A002619(2*n + 1)/2 for n > 0; a(2*n) = (A002619(2*n) + A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 17 2019
a(n) ~ sqrt(2*Pi)/2 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

Added a(1) = 1 and a(2) = 1 by Gus Wiseman, Mar 02 2019

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

Original entry on oeis.org

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

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.

Original entry on oeis.org

1, 2, 4, 22, 208, 5560, 299600, 33562696, 7635498336, 3518440564544, 3275345183542208, 6148914696963883712, 23248573454127484129024, 176848577040808821410837120, 2704321280486889389864215362560, 83076749736557243209409446411255936, 5124252113632955685095523500148980125696, 634332307869315502692705867068871886072665600

Offset: 1

N. J. A. Sloane, Jun 28 2011

nonn

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

			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)

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.

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.

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)];

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

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

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

A323865 Number of aperiodic binary toroidal necklaces of size n.

Original entry on oeis.org

1, 2, 2, 4, 8, 12, 36, 36, 114, 166, 396, 372, 1992, 1260, 4644, 8728, 20310, 15420, 87174, 55188, 314064, 399432, 762228, 729444, 5589620, 4026522, 10323180, 19883920, 57516048, 37025580, 286322136, 138547332, 805277760, 1041203944, 2021145660, 3926827224

Offset: 0

Gus Wiseman, Feb 04 2019

nonn

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

			Inequivalent representatives of the a(6) = 36 aperiodic necklaces:
  000001  000011  000101  000111  001011  001101  001111  010111  011111
.
  000  000  001  001  001  001  001  011  011
  001  011  010  011  101  110  111  101  111
.
  00  00  00  00  00  01  01  01  01
  00  01  01  01  11  01  01  10  11
  01  01  10  11  01  10  11  11  11
.
  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  1  1
  0  0  0  0  1  1  1  0  1
  0  0  1  1  0  1  1  1  1
  0  1  0  1  1  0  1  1  1
  1  1  1  1  1  1  1  1  1

Andrew Howroyd, Table of n, a(n) for n = 0..200
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Cf. A000031, A001037, A027375, A179043, A184271, A323351.

Cf. A323858, A323859, A323860, A323861, A323864, A323871.

apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
zaz[n_]:=Join@@(Table[Partition[#,d],{d,Divisors[n]}]&/@Tuples[{0,1},n]);
Table[If[n==0,1,Length[Union[First/@matcyc/@Select[zaz[n],And[apermatQ[#],neckmatQ[#]]&]]]],{n,0,10}]

a(n) = Sum_{d|n} A323861(d, n/d) for n > 0. - Andrew Howroyd, Aug 21 2019

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

A323870 Number of toroidal necklaces of size n whose entries cover an initial interval of positive integers.

Original entry on oeis.org

1, 4, 10, 61, 218, 3136, 13514, 272998, 2362439, 40899248, 295024106, 14045787790, 81055130522, 3040383719360, 61408850927732, 1661142088494553, 15337737297545402, 1128511554421317128, 9768588138876674858, 803306338873366385030, 15452347618762680757428

Offset: 1

Gus Wiseman, Feb 04 2019

nonn

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. Alternatively, a toroidal necklace is a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns.

			The a(3) = 10 toroidal necklaces:
  [1 2 3] [1 3 2] [1 2 2] [1 1 2] [1 1 1]
.
  [1] [1] [1] [1] [1]
  [2] [3] [2] [1] [1]
  [3] [2] [2] [2] [1]

Andrew Howroyd, Table of n, a(n) for n = 1..200
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Cf. A000670, A008965, A060223.

Cf. A323858, A323859, A323866, A323868, A323871.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[Length[Select[nrmmats[n],neckmatQ]],{n,6}]

U(n,m,k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))));
R(v)={sum(n=1, #v, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*v[k]))}
a(n)={if(n < 1, n==0, R(vector(n, k, sumdiv(n, d, U(d, n/d, k))) ))} \\ Andrew Howroyd, Aug 18 2019

Terms a(9) and beyond from Andrew Howroyd, Aug 18 2019

A323859 Number of binary toroidal necklaces of size n.

Original entry on oeis.org

1, 2, 6, 8, 19, 16, 56, 40, 152, 184, 432, 376, 2132, 1264, 4728, 8768, 20688, 15424, 87656, 55192, 315128, 399520, 762984, 729448, 5595408, 4026576, 10325712, 19884504, 57527804, 37025584, 286340544, 138547336, 805335364, 1041204704, 2021176512, 3926827328

Offset: 0

Gus Wiseman, Feb 04 2019

nonn

The 1-dimensional (necklace) case is A000031.

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. Alternatively, a toroidal necklace is a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns.

			Inequivalent representatives of the a(4) = 19 binary toroidal necklaces:
  [0 0 0 0] [0 0 0 1] [0 0 1 1] [0 1 0 1] [0 1 1 1] [1 1 1 1]
.
  [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
  [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]
.
  [0] [0] [0] [0] [0] [1]
  [0] [0] [0] [1] [1] [1]
  [0] [0] [1] [0] [1] [1]
  [0] [1] [1] [1] [1] [1]

Andrew Howroyd, Table of n, a(n) for n = 0..1000
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Cf. A000031, A008965, A179043, A184271, A323351.

Cf. A323858, A323859, A323865, A323870.

matcyc[m_]:=Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
Table[If[n==0,1,Length[Union[First/@matcyc/@Join@@(Table[Partition[#,d],{d,Divisors[n]}]&/@Tuples[{0,1},n])]]],{n,0,10}]

U(n, m, k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))))
a(n) = if(n<1, n==0, sumdiv(n, d, U(n/d, d, 2))) \\ Andrew Howroyd, Jan 24 2023

a(n) = (1/n) * Sum_{d|n} Sum_{e|d, f|(n/d)} phi(e) * phi(f) * 2^(n/lcm(d,n/d)). [Ethier]

A323871 Number of aperiodic toroidal necklaces of size n whose entries cover an initial interval of positive integers.

Original entry on oeis.org

1, 2, 8, 53, 216, 3112, 13512, 272844, 2362412, 40898808, 295024104, 14045779864, 81055130520, 3040383692328, 61408850927280, 1661142087743940, 15337737297545400, 1128511554416582908, 9768588138876674856, 803306338873264137240, 15452347618762680730384

Offset: 1

Gus Wiseman, Feb 04 2019

nonn

The 1-dimensional (Lyndon word) case is A060223.

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

			The a(3) = 8 aperiodic toroidal necklaces:
  [1 2 3] [1 3 2] [1 2 2] [1 1 2]
.
  [1] [1] [1] [1]
  [2] [3] [2] [1]
  [3] [2] [2] [2]

Andrew Howroyd, Table of n, a(n) for n = 1..200
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Cf. A000670, A000740, A008965, A060223.

Cf. A323858, A323859, A323860, A323861, A323866, A323867, A323868, A323870.

List([1..30], A323871); # See A323861 for code; Andrew Howroyd, Aug 21 2019

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[Length[Select[nrmmats[n],neckmatQ[#]&&apermatQ[#]&]],{n,6}]

Terms a(9) and beyond from Andrew Howroyd, Aug 21 2019

A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

Original entry on oeis.org

1, 1, 1, 4, 12, 64, 360, 2544, 20160, 181632

Offset: 1

Olivier Gérard, Jul 31 2016

Let us consider two permutations to be equivalent if they can be obtained from each other by cyclic rotation (12345->(23451,34512,45123,51234) or n+1-complement (31254->35412), or a combination of those two transformations (they commute with each other). a(n) is the number of classes.
We obtain the same number of classes if the transformations are (addition of a constant modulo n and reversal (12345->54321)) but not the same set of representatives.
It seems probable that a(2n+1) = (2n)!/2
This sequence may be related to A113247 (and A113248) as they share a common dissection 1, 4, 64, 2544, 181632. The fact that they count permutation classes for the major index is a further indication.
Number of path necklaces, defined as equivalence classes of (labeled, undirected) Hamiltonian paths under rotation of the vertices. The cycle version is A000939. - Gus Wiseman, Mar 02 2019

			Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.
n=4 case addition mod n and reversal
1234, 1243, 1324, 1423.
n=4 case rotation and complement
1234, 1243, 1324, 1342.
.
n=5 case addition mod n and reversal
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.
n=5 case rotation and complement
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.

Wikipedia, Hamiltonian path.
Wikipedia, Necklace (combinatorics).
Gus Wiseman, Inequivalent representatives of the a(5) = 12 path necklaces.
Gus Wiseman, Inequivalent representatives of the a(6) = 54 path necklaces.

Cf. A000939, A000940, A002619, A089066, A262480 (other symmetry classes of permutations).
Cf. A193651 (inspiration for a(2n)).
Cf. A000031, A006125, A008965, A059966, A060223, A192332, A323858, A323870, A324461.

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

(Conjecture). If n odd a(n)=((n - 1))!/2. If n even a(n)= 1/2 (n - 2)!! (1 + ( n - 1)!!).

cp's OEIS Frontend

A184271 Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal binary arrays (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A179043 Number of n X n checkered tori.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A000939 Number of inequivalent n-gons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A323865 Number of aperiodic binary toroidal necklaces of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions