A328150 Number of n-bead necklace structures with no adjacent elements having the same color.

1, 0, 1, 1, 3, 3, 12, 24, 103, 387, 1819, 8933, 48632, 279484, 1716523, 11126025, 76014437, 544945399, 4089010392, 32025053060, 261213946739, 2214280580389, 19471365925297, 177319383231697, 1669735890602062, 16235408370162588, 162796351456044465, 1681427459283678177

Offset

0,5

Comments

Beads may be of any number of colors. Colors may be permuted without changing the necklace structure.

Equivalently, the number of set partitions of an n-set up to rotations where no block contains cyclically adjacent elements of the n-set.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Example

a(6) = 12 because there are the following 12 necklace structures: ABABAB, ABABAC, ABABCD, ABACAD, ABACBC, ABACBD, ABACDC, ABACDE, ABCABC, ABCABD, ABCADE, ABCDEF.

Prog

(PARI) seq(n)={Vec(1 + intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(-x + sumdiv(m, d, (exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))} \\ Andrew Howroyd, Oct 09 2019

Crossrefs

Row sums of A327396.

Cf. A084423.

Sequence in context: A136533 A268639 A192307 * A161804 A097342 A370145

Adjacent sequences: A328147 A328148 A328149 * A328151 A328152 A328153

Keyword

nonn

Author

Andrew Howroyd, Oct 05 2019

Extensions

Terms a(16) and beyond from Andrew Howroyd, Oct 09 2019

Status

approved