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

Author

Christian G. Bower

Keywords

• nonn

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

• Ray Chandler, Table of n, a(n) for n = 12..1012
• 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
• Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1,1,-10,45,-120,210,-252,210,-120,45,-10,1).

Crossrefs

A column of triangle A011847.

Programs

Mathematica

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

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