|
|
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
|
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
|
|
|
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
|
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. A000031, A000939 (cycle necklaces), A008965, A059966, A060223, A061417, A086675 (digraph version), A184271, A275527, A323858, A324461, A324463, A324464.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|