login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032168 Number of aperiodic necklaces of n beads of 2 colors, 10 of them black. 7
1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, 16796, 29372, 49742, 81686, 130750, 204248, 312455, 468611, 690690, 1001400, 1430715, 2015871, 2804880, 3856528, 5245125, 7060508, 9414328, 12440056, 16301164 (list; graph; refs; listen; history; text; internal format)
OFFSET

11,2

COMMENTS

From Petros Hadjicostas, Aug 24 2018: (Start)

It can be proved that the CHK[k] transform of sequence (c(n): n>=1) has generating function A_k(x) = (1/k)*Sum_{d|k} mu(d)*C(x^d)^{k/d}, where C(x) = Sum_{n>=1} c(n)*x^n is the g.f. of (c(n): n>=1).

When c(n) = 1 for all n >= 1, we get C(x) = x/(1-x) and A_k(x) = (x^k/k)*Sum_{d|k} mu(d)*(1-x^d)^{-k/d}, which is Herbert Kociemba's general formula (in the Mathematica code) for a_k(n), the number of aperiodic necklaces of n beads of 2 colors with k of them black and n-k of them white.

Using Taylor expansions, we can easily prove that 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).

For this sequence k = 10, and thus we get the formulae below.

(End)

LINKS

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

C. G. Bower, Transforms (2)

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

Index entries for sequences related to Lyndon words

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

FORMULA

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

G.f.:  x^10*(1/(1-x)^10 - 1/(1-x^2)^5 - 1/(1-x^5)^2 + 1/(1-x^10))/10. - Herbert Kociemba, Oct 23 2016

a(n) = (1/10)*(binomial(n-1, 9) - I(2|n)*binomial(floor(n/2) - 1, 4) - I(5|n)*(floor(n/5) - 1) + I(10|n)), where I(a|b) = 1 if integer a divides integer b, and 0 otherwise. - Petros Hadjicostas, Aug 25 2018

EXAMPLE

From Petros Hadjicostas, Aug 24 2018: (Start)

According to Bower's theory in the web link above, we have exactly k = 10 boxes of different sizes and colors that are placed on a circle. Two boxes are considered identical if they have the same number of balls (i.e., the same size) and the same color. Here c(n) = 1 for all n >= 1, which means all k boxes have at least one ball and only one color. Two configurations of k boxes on the circle with n balls in total are considered equivalent iff one can be obtained from the other by rotation. Since we are dealing with the CHK[k] transform, the configuration of k boxes on the circle must be aperiodic. (This is the meaning of H when we are dealing with order C, i.e., with necklaces. The letter K means that the balls are unlabeled.)

Here, a(n) equals the number of non-equivalent aperiodic configurations of k boxes on the circle (necklaces with k boxes) such that (i) the total number of balls is n, (ii) each box has at least one ball, and (iii) all balls are unlabeled.

Thus, a(n) is the number of unmarked aperiodic cyclic compositions of n with k = 10 positive parts. (The word "umarked" means that two cyclic compositions are equivalent if one can be obtained from the other by rotation.)

Let b_1,b_2,...,b_k be such a cyclic aperiodic composition of n. By definition, b_i >= 1 for i=1,...,k. On a circle, start with a black ball, and place b_1 - 1 white balls to the right of the black ball; then place one black ball followed by b_2 - 1 white balls; continue this until you have a black ball followed by b_k - 1 white balls on the circle. The last white ball (if any) is followed by the first black ball. (If b_k = 1, then the last black ball is followed by the first black ball.) If the position of the first black ball is unmarked, then we may freely rotate the configuration of black and white balls on the circle. We thus get an aperiodic necklace with n balls (or beads) of 2 colors, k = 10 of which are black and n - k = n - 10 of which are white. (We assume of course that n >= 10. Since each necklace is aperiodic, we must have n >= 11 since the configuration b_i = 1 for all i is not allowed.)

The above argument shows that, for n >= k+1 = 11, a(n) is the number of aperiodic necklaces of n beads of 2 colors such that k = 10 of them are black and the rest are white.

For n = 11, a(11) = 1, because we have only one unmarked aperiodic cyclic composition of n = 11 with k = 10 parts and only one aperiodic necklace with 11 beads such that k = 10 of them are black and n-k = 1 of them is white: 2111111111 <-> BWBBBBBBBBB.

For n = 12, a(12) = 5, because we have the following aperiodic cyclic compositions and corresponding aperiodic necklaces:

(1) 3111111111 <-> BWWBBBBBBBBB

(2) 2211111111 <-> BWBWBBBBBBBB

(3) 2121111111 <-> BWBBWBBBBBBB

(4) 2112111111 <-> BWBBBWBBBBBB

(5) 2111211111 <-> BWBBBBWBBBBB

(The configuration 2111121111 <-> BWBBBBBWBBBB is excluded because, on a circle, it has period 2.)

(End)

MATHEMATICA

(* The g.f. given above is the special case k=10 for *)

gf[x_, k_]:=x^k/k Plus@@(MoebiusMu[#](1-x^#)^(-(k/#))&/@Divisors[k])

(* which gives the  g.f. for the number of aperiodic necklaces of n beads of 2 colors, k of them black. *) (* Herbert Kociemba, Oct 23 2016 *)

CoefficientList[Series[(1/x)*(1/(1 - x)^10 - 1/(1 - x^2)^5 - 1/(1 - x^5)^2 + 1/(1 - x^10))/10, {x, 0, 50}], x] (* Stefano Spezia, Aug 31 2018 *)

CROSSREFS

Sequence in context: A222632 A273336 A273768 * A246211 A000345 A011846

Adjacent sequences:  A032165 A032166 A032167 * A032169 A032170 A032171

KEYWORD

nonn

AUTHOR

Christian G. Bower

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 08:12 EST 2018. Contains 318049 sequences. (Running on oeis4.)