|
| |
|
|
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
|
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
|
|
|
|
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
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
