login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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.

Sequence in context: A283322 A019025 A264729 * A324603 A322520 A018279

Adjacent sequences:  A192329 A192330 A192331 * A192333 A192334 A192335

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jun 28 2011

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 25 02:54 EST 2020. Contains 332217 sequences. (Running on oeis4.)