A192332 -id:A192332 - cp's OEIS frontend

A192314 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 nonempty subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=0, a(2)=1 by convention.

0, 1, 3, 21, 207, 5559, 299599, 33562695, 7635498335, 3518440564543, 3275345183542207, 6148914696963883711, 23248573454127484129023, 176848577040808821410837119, 2704321280486889389864215362559, 83076749736557243209409446411255935, 5124252113632955685095523500148980125695, 634332307869315502692705867068871886072665599, 157534492276509956656902449336997243381860518317055

Offset: 1

David N Lumsden, Jun 27 2011

nonn

This is the number of ways to sew on a button having n holes arranged in a regular polygon. A button with no stitches would fall off, which is why we require that the subset be nonempty (cf. A192332).

A. Kolmogorov posed the problem for n=4 at the age of 6.

A. N. Shiryaev 'Andrei Nikolaevich Kolmogorov: A Biographical Sketch of His Life and Creative Paths' in Harold H. McFaden (translator), Kolmogorov in Perspective, American Mathematical Society (2000), page 4.

Vincenzo Librandi, Table of n, a(n) for n = 1..80

Cf. A192332, A191563.

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)-1, n=1..30)];
# N. J. A. Sloane, Jun 28 2011

Table[ -1 + 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 *)

a(p) = ((2^(p*(p-1)/2) - 2^((p-1)/2)) / p) + (2^((p-1)/2)) - 1 if p is prime.

Comment from N. J. A. Sloane, Jun 28 2011: More generally, 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))) - 1.

Terms from a(8) onwards from N. J. A. Sloane, Jun 28 2011

A191563 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 or reflection are regarded as identical). a(1)=1, a(2)=2 by convention.

Original entry on oeis.org

1, 2, 4, 19, 136, 3036, 151848, 16814116, 3818273456, 1759237059488, 1637673128642016, 3074457382841680224, 11624286729262765320064, 88424288520685885682129216, 1352160640243480723729126645248, 41538374868278630828076760060403776, 2562126056816477844908944991509312669696

Offset: 1

N. J. A. Sloane, Jun 29 2011

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..80
Marc Moskowitz, Unique connections of N circularly-spaced points, Feb 05, 2011

Suggested by A192314. See A192332 for orbits under cyclic group.

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;
if n mod 2 = 0 then t0:=t0+n*2^(n^2/4)
else t0:=t0+n*2^((n^2-1)/4); fi;
t0/(2*n); end;
s1:=[seq(f(n),n=1..20)];

Table[(2^((n^2-Mod[n,2])/4) + 1/n*(Plus@@ Map[Function[d,EulerPhi[d]*2^((n*(n-Mod[d,2])/2)/d)],Divisors[n]]))/2, {n,1,20}] (* From Olivier Gérard, Aug 27 2011 *)

See Maple program.

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

A218144 Number of inequivalent graphs on n nodes where two graphs are equivalent if adjacency is preserved under the action of the alternating group.

Original entry on oeis.org

1, 2, 4, 12, 40, 184, 1296, 17072, 424992, 20314096, 1836858752, 310029536960, 97286240288512, 56843800957620672, 62057188173197829888, 127071179605916892107264, 489838590133142165412740096, 3566828190793813383233169950592, 49211415580467941255510544567667200

Offset: 1

Geoffrey Critzer, Oct 21 2012

nonn

			a(4) = 12 because we have the 11 classes of graphs (A000088) under the action of the symmetric group but the class represented by (say) 1-2-3-4 is separate from the class of graphs that could be represented by 2-1-3-4.

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A000088, A192332, A191563, A199574.

CoefficientList[Table[PairGroupIndex[AlternatingGroup[n],s]/.Table[s[i]->2,{i,1,Binomial[n,2]}],{n,1,7}],x]
(* Second program: *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!); a[1] = 1;
a[n_] := (s = 0; Do[If[EvenQ[Total[p - 1]], s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; 2*s/n!);
Array[a, 20] (* Jean-François Alcover, Jul 09 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, if(sum(i=1,#p,p[i]-1)%2==0, s+=permcount(p)*2^edges(p))); if(n==1, 1, 2*s/n!)} \\ Andrew Howroyd, May 22 2018

Terms a(11) and beyond from Andrew Howroyd, May 22 2018

A306715 Number of graphical necklaces with n vertices and distinct rotations.

Original entry on oeis.org

1, 0, 2, 12, 204, 5372, 299592, 33546240, 7635496960, 3518433853392, 3275345183542176, 6148914685509544960, 23248573454127484128960, 176848577040728399988915648, 2704321280486889389857342715776, 83076749736557240903566436660674560

Offset: 1

Gus Wiseman, Mar 05 2019

nonn

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.

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.

Cf. A000088, A001037, A006125, A059966, A060223, A086675, A192332 (graphical necklaces), A306669, A323861, A323865, A323866, A323871, A324461 (distinct rotations), A324513.

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}]

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

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

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

cp's OEIS Frontend

A192314 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 nonempty subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=0, a(2)=1 by convention.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A191563 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 or reflection are regarded as identical). a(1)=1, a(2)=2 by convention.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A324512 Number of aperiodic n-gons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A218144 Number of inequivalent graphs on n nodes where two graphs are equivalent if adjacency is preserved under the action of the alternating group.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A306715 Number of graphical necklaces with n vertices and distinct rotations.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A192314 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 nonempty subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=0, a(2)=1 by convention.