A227910 The number of necklaces with n beads of white and red colors, including at least three white ones.

1, 2, 4, 8, 13, 24, 40, 71, 119, 216, 372, 678, 1215, 2240, 4102, 7674, 14299, 27000, 50952, 96896, 184397, 352684, 675174, 1296843, 2493711, 4806062, 9272764, 17920843, 34669585, 67159032, 130216106, 252745349, 490984469, 954637538, 1857545280, 3617214660, 7048675939, 13744694906

Offset: 3

Author

Vladimir Letsko, Oct 13 2013

Keywords

• nonn

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

Examples

			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.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 3..200
• Peter Kagey, Examples of classes of n-gons for a(4), a(5), and a(6)
• Vladimir Letsko, Mathematical Marathon, Problem 150 (in Russian)

Crossrefs

Cf. A000029, A262232.

Programs

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 *)

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

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.