

A263768


Number of necklaces with n beads colored white or red, where the number of white beads is odd and at least three and turning over is allowed.


1



1, 1, 3, 4, 8, 11, 22, 33, 62, 101, 189, 324, 611, 1087, 2055, 3770, 7154, 13363, 25481, 48174, 92204, 175791, 337593, 647325, 1246862, 2400841, 4636389, 8956059, 17334800, 33570815, 65108061, 126355335, 245492243, 477284181, 928772649, 1808538354, 3524337979, 6872209823
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,3


COMMENTS

a(n) is also the number of nonisomorphic nvertex undirected graphs forming an odd cycle with any number of degree1 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 each pendant vertex attached to the next clockwise cycle vertex. Since these are exactly the graphs of the nvertex and nedge linear thrackles, a(n) is also the number of nonisomorphic linear thrackles.
For any n there is a unique nbead necklace where the number of white beads is 1. Hence this sequence is one less than the number of nbead (0,1) bracelets with an odd number of 0's.  Andrew Howroyd, Feb 28 2017


LINKS

Andrew Howroyd, Table of n, a(n) for n = 3..100


FORMULA

a(n) = (A000016(n) + A016116(n1)) / 2  1.  Andrew Howroyd, Feb 28 2017


EXAMPLE

For n=5 the a(5)=3 solutions are: five white beads (a 5cycle), three white beads and two red beads with the two red beads adjacent (a triangle with two pendant vertices attached at one triangle vertex), and three white beads and two red beads with the two red beads separated (a triangle with two of its vertices having a single pendant vertex attached).


CROSSREFS

Cf. A227910, A007147, A000016.
Sequence in context: A109794 A034417 A126873 * A050316 A161538 A319980
Adjacent sequences: A263765 A263766 A263767 * A263769 A263770 A263771


KEYWORD

nonn


AUTHOR

David Eppstein, Oct 25 2015


EXTENSIONS

a(21)a(40) from Andrew Howroyd, Feb 28 2017


STATUS

approved



