cp's OEIS Frontend

A032168 Number of aperiodic necklaces of n beads of 2 colors, 10 of them black.

%I A032168 #79 Feb 23 2025 09:56:56
%S A032168 1,5,22,70,200,497,1144,2424,4862,9225,16796,29372,49742,81686,130750,
%T A032168 204248,312455,468611,690690,1001400,1430715,2015871,2804880,3856528,
%U A032168 5245125,7060508,9414328,12440056,16301164
%N A032168 Number of aperiodic necklaces of n beads of 2 colors, 10 of them black.
%C A032168 From _Petros Hadjicostas_, Aug 24 2018: (Start)
%C A032168 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).
%C A032168 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.
%C A032168 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).
%C A032168 For this sequence k = 10, and thus we get the formulae below.
%C A032168 (End)
%H A032168 Ray Chandler, <a href="/A032168/b032168.txt">Table of n, a(n) for n = 11..1011</a>
%H A032168 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A032168 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A032168 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A032168 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%H A032168 <a href="/index/Rec#order_27">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-12,17,9,-32,10,29,-29,-9,28,-7,-5,-5,-7,28,-9,-29,29,10,-32,9,17,-12,-2,4,-1).
%F A032168 "CHK[ 10 ]" (necklace, identity, unlabeled, 10 parts) transform of 1, 1, 1, 1, ...
%F A032168 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
%F A032168 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
%e A032168 From _Petros Hadjicostas_, Aug 24 2018: (Start)
%e A032168 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.)
%e A032168 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.
%e A032168 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.)
%e A032168 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.)
%e A032168 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.
%e A032168 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.
%e A032168 For n = 12, a(12) = 5, because we have the following aperiodic cyclic compositions and corresponding aperiodic necklaces:
%e A032168 (1) 3111111111 <-> BWWBBBBBBBBB
%e A032168 (2) 2211111111 <-> BWBWBBBBBBBB
%e A032168 (3) 2121111111 <-> BWBBWBBBBBBB
%e A032168 (4) 2112111111 <-> BWBBBWBBBBBB
%e A032168 (5) 2111211111 <-> BWBBBBWBBBBB
%e A032168 (The configuration 2111121111 <-> BWBBBBBWBBBB is excluded because, on a circle, it has period 2.)
%e A032168 (End)
%t A032168 (* The g.f. given above is the special case k=10 for *)
%t A032168 gf[x_,k_]:=x^k/k Plus@@(MoebiusMu[#](1-x^#)^(-(k/#))&/@Divisors[k])
%t A032168 (* 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 *)
%t A032168 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 *)
%K A032168 nonn
%O A032168 11,2
%A A032168 _Christian G. Bower_