OFFSET
3,2
COMMENTS
a(n) is the number of classes (not necessarily convex) n-gons. Two n-gons are assigned to the same class, if (under suitable start and direction) their vertex at the same time belong or do not belong to the convex hull of the corresponding polygon.
a(n) is also the number of classes (not necessarily convex) n-gons at the other classification. Two n-gons belong to one class, if (under suitable start and direction) their angles simultaneously have a measure either less or greater than 180 degrees.
Note that the equation quantities of classes of these classifications does not mean equality classes themselves.
a(n) is also the number of non-isomorphic n-vertex undirected graphs in the form of a simple cycle with any number of degree-1 vertices attached to each cycle vertex. To transform a necklace into a graph of this type, create a cycle vertex for each white bead and a pendant vertex for each red bead, with the pendant vertex for a red bead attached to the cycle vertex for the clockwise next white bead. - David Eppstein, Oct 25 2015
LINKS
Andrew Howroyd, Table of n, a(n) for n = 3..200
Vladimir Letsko, Mathematical Marathon, Problem 150 (in Russian)
FORMULA
a(n) = (Sum_{m=3..n} (1/n*sum_{d|gcd(m,n)} phi(d)*binomial(n/d,m/d)) + binomial(floor(m/2)+floor((n-m)/2), floor(m/2)))/2.
EXAMPLE
a(4)=2 because there are exactly 2 necklaces with 4 beads of white and red colors, including at least three white ones:
1) all beads are white;
2) one bead is red.
MAPLE
g:=(n, m)->add(phi(d)*binomial(n/d, m/d), d in divisors(igcd(n, m)))/2/n+1/2*binomial(floor(m/2)+floor((n-m)/2), floor(m/2));
for n from 3 do s:=0:for m from 3 to n dos:=s+g(n, m) od: print(n, s) od:
MATHEMATICA
g[n_, m_] := Sum[EulerPhi[d]*Binomial[n/d, m/d], {d , Divisors[GCD[n, m]]}]/2/n + 1/2*Binomial[Floor[m/2] + Floor[(n - m)/2], Floor[m/2]];
A227910 = Table[Sum[g[n, m], {m, 3, n}], {n, 3, 40}] (* Jean-François Alcover, Jul 02 2018, from Maple *)
PROG
(PARI) a(n) = (sum(m=3, n, (1/n*sumdiv(gcd(m, n), d, eulerphi(d)*binomial(n/d, m/d))) + binomial(m\2+(n-m)\2, m\2) ))/2; \\ Andrew Howroyd, Oct 11 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Letsko, Oct 13 2013
STATUS
approved