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

Author

Andrew Howroyd, Oct 05 2019

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

Row sums of A327396.

Cf. A084423.

Programs

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

Extensions

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