A323858 -id:A323858 - cp's OEIS frontend

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

1, 1, 1, 3, 5, 12, 18, 42, 72, 145, 262, 522, 960, 1879, 3531, 6831, 13013, 25148, 48177, 93186, 179507, 347509, 671955, 1303257, 2527162, 4910681, 9545176, 18579471, 36183505, 70540861, 137603801, 268655547, 524842088, 1026067205, 2007118657, 3928564113

Offset: 0

Gus Wiseman, Feb 04 2019

nonn

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

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) = 18 toroidal necklaces:
  [6] [1 5] [2 4] [1 1 4] [1 2 3] [1 3 2] [1 1 1 3] [1 1 2 2] [1 1 1 1 2]
.
  [1] [2] [1 1]
  [5] [4] [1 3]
.
  [1] [1] [1]
  [1] [2] [3]
  [4] [3] [2]
.
  [1] [1]
  [1] [1]
  [1] [2]
  [3] [2]
.
  [1]
  [1]
  [1]
  [1]
  [2]

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, A000670, A000740, A001037, A008965, A059966, A060223, A185700.

Cf. A323858, A323861, A323865, A323871.

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

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
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[If[n==0,1,Length[Union@@Table[Select[ptnmats[k],And[apermatQ[#],neckmatQ[#]]&],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]]],{n,0,10}]

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

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

A324463 Number of graphical necklaces covering n vertices.

Original entry on oeis.org

1, 0, 1, 2, 15, 156, 4665, 269618, 31573327, 7375159140, 3450904512841, 3240500443884718, 6113078165054644451, 23175001880311842459108, 176546824267008236554238517, 2701847513793569606737940203894, 83036203475880811677609125194805687

Offset: 0

Gus Wiseman, Feb 28 2019

nonn

A graphical necklace is 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. Covering means there are no isolated vertices. These are a kind of partially labeled graphs.

			Inequivalent representatives of the a(2) = 1 through a(4) = 15 graphical necklaces:
  {{12}}  {{12}{13}}      {{12}{34}}
          {{12}{13}{23}}  {{13}{24}}
                          {{12}{13}{14}}
                          {{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}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 15 covering graphical necklaces, radial embedding.
Gus Wiseman, The a(5) = 156 covering graphical necklaces.

Cf. A000031, A002494, A006129, A008965, A184271, A192332 (non-covering case), A323858, A323859, A323870, A324461, A324462, A324464.

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

a(n)={if(n<1, n==0, sumdiv(n, d, eulerphi(n/d)*sum(k=0, d, (-1)^(d-k)*binomial(d,k)*2^(k*(k-1)*n/(2*d) + k*(n/d\2))))/n)} \\ Andrew Howroyd, Aug 19 2019

a(n) = (1/n)*Sum{d|n} phi(n/d) * Sum_{k=0..d} (-1)^(d-k)*binomial(d,k)*2^( k*(k-1)*n/(2*d) + k*(floor(n/(2*d))) ). - Andrew Howroyd, Aug 19 2019

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

A324464 Number of connected graphical necklaces with n vertices.

Original entry on oeis.org

1, 0, 1, 2, 13, 148, 4530, 266614, 31451264, 7366255436, 3449652145180, 3240150686268514, 6112883022923529310, 23174784819204929919428, 176546343645071836902594288, 2701845395848698682311893154024, 83036184895986451215378727412638816, 5122922885438069578928905234650082410736

Offset: 0

Gus Wiseman, Mar 01 2019

nonn

			Inequivalent representatives of the a(2) = 1 through a(4) = 13 graphical necklaces:
  {{12}}  {{12}{13}}      {{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}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 13 connected graphical necklaces.
Gus Wiseman, The a(5) = 148 connected graphical necklaces.

Cf. A000031, A000939, A001187, A006125, A006129, A008965, A184271, A192332, A275527, A323858, A323859, A323870, A324461, A324462, A324463.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[csm[#]]<=1,#=={}||#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]]&]],{n,0,5}]

\\ B(n,d) is graphs on n*d points invariant under 1/d rotation.
B(n,d)={2^(n*(n-1)*d/2 + n*(d\2))}
D(n,d)={my(v=vector(n, i, B(i,d)), u=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); sumdiv(n, e, eulerphi(d*e) * moebius(e) * u[n/e] * e^(n/e-1))}
a(n)={if(n<=1, n==0, sumdiv(n, d, D(n/d,d))/n)} \\ Andrew Howroyd, Jan 24 2023

Terms a(7) and beyond from Andrew Howroyd, Jan 24 2023

cp's OEIS Frontend

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

Extensions

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

A324463 Number of graphical necklaces covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A324464 Number of connected graphical necklaces with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions