A032169 Number of aperiodic necklaces of n beads of 2 colors, 11 of them black.

1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32065, 58786, 104006, 178296, 297160, 482885, 766935, 1193010, 1820910, 2731365, 4032015, 5864749, 8414640, 11920740, 16689036, 23107896, 31666376, 42975796

Offset

12,2

Comments

From Petros Hadjicostas, Aug 26 2018: (Start)

Assume n >= k >= 2. If a_k(n) is the number of aperiodic necklaces of n beads of 2 colors such that k of them are black and n-k of them are white, then a_k(n) = (1/k)*Sum_{d|gcd(n,k)} mu(d)*binomial(n/d - 1, k/d - 1) = (1/n)*Sum_{d|gcd(n,k)} mu(d)*binomial(n/d, k/d). This follows from Herbert Kociemba's general formula for the g.f. of (a_k(n): n>=1) that can be found in the comments for sequence A032168.

For k prime, we get a_k(n) = floor(binomial(n-1, k-1)/k). In such a case, the sequence becomes a column for triangle A011847. (This is not true when k is composite >= 4.)

(End)

Links

Table of n, a(n) for n=12..39.

C. G. Bower, Transforms (2)

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

Index entries for sequences related to Lyndon words

Formula

"CHK[ 11 ]" (necklace, identity, unlabeled, 11 parts) transform of 1, 1, 1, 1, ...

G.f.: (x^11/11)*(1/(1-x)^11-1/(1-x^11)). - Herbert Kociemba, Oct 16 2016

a(n) = (1/11)*(binomial(n-1, 10) - I(11|n)) = floor(binomial(n-1, 10)/11) for n >= 12, where I(a|b) = 1 if integer a divides integer b, and 0 otherwise. - Petros Hadjicostas, Aug 26 2018

Mathematica

CoefficientList[Series[x^11/11 (1/(1-x)^11-1/(1- x^11)), {x, 0, 50}], x] (* Herbert Kociemba, Oct 16 2016 *)

Crossrefs

A column of triangle A011847.

Sequence in context: A060101 A036422 A166214 * A032196 A011780 A036631

Adjacent sequences: A032166 A032167 A032168 * A032170 A032171 A032172

Keyword

nonn

Author

Christian G. Bower

Status

approved