|
| |
|
|
A227910
|
|
The number of necklaces with n beads of white and red colors, including at least three white ones.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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]];
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
