A032191 - OEIS

%I #72 Apr 04 2024 10:13:10

%S 1,1,4,10,22,42,80,132,217,335,504,728,1038,1428,1944,2586,3399,4389,

%T 5620,7084,8866,10966,13468,16380,19811,23751,28336,33566,39576,46376,

%U 54132,62832,72675,83661,95988,109668,124936,141778

%N Number of necklaces with 6 black beads and n-6 white beads.

%C The g.f. is Z(C_6,x)/x^6, the 6-variate cycle index polynomial for the cyclic group C_6, with substitution x[i]->1/(1-x^i), i=1,...,6. Therefore by Polya enumeration a(n+6) is the number of cyclically inequivalent 6-necklaces whose 6 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_6,x). Note the equivalence of this formulation with the one given as this sequence's name: start with a black 6-necklace (all 6 beads have labels 0). Insert after each of the 6 black beads k white ones if the label was k and then disregard the labels. - _Wolfdieter Lang_, Feb 15 2005

%C The g.f. of the CIK[k] transform of the sequence (b(n): n>=1), which has g.f. B(x) = Sum_{n>=1} b(n)*x^n, is CIK[k](x) = (1/k)*Sum_{d|k} phi(d)*B(x^d)^{k/d}. Here, k = 6, b(n) = 1 for all n >= 1, and B(x) = x/(1-x), from which we get another proof of the g.f.s given below. - _Petros Hadjicostas_, Jan 07 2018

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%H Christian Meyer, <a href="/A032191/a032191.pdf">On conjecture no. 75 arising from the OEIS</a>, preprint, 2004. [cached copy]

%H Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, <a href="https://arxiv.org/abs/2403.20148">A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions</a>, arXiv:2403.20148 [math.CO], 2024. See p. 6.

%H Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0409509">Prove or disprove: 100 conjectures from the OEIS</a>, arXiv:math/0409509 [math.CO], 2004.

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%H <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-3,-1,1,4,-3,-3,4,1,-1,-3,1,2,-1).

%F "CIK[ 6 ]" (necklace, indistinct, unlabeled, 6 parts) transform of 1, 1, 1, 1, ...

%F G.f.: (1-x+x^2+4*x^3+2*x^4+3*x^6+x^7+x^8)/((1-x)^6*(1+x)^3*(1+x+x^2)^2*(1-x+x^2)) (conjectured). - _Ralf Stephan_, May 05 2004

%F G.f.: (x^6)*(1-x+x^2+4*x^3+2*x^4+3*x^6+x^7+x^8)/((1-x)^2*(1-x^2)^2*(1-x^3)*(1-x^6)). (proving the R. Stephan conjecture (with the correct offset) in a different version; see Comments entry above). - _Wolfdieter Lang_, Feb 15 2005

%F G.f.: (1/6)*x^6*((1-x)^(-6)+(1-x^2)^(-3)+2*(1-x^3)^(-2)+2*(1-x^6)^(-1)). - _Herbert Kociemba_, Oct 22 2016

%e From _Petros Hadjicostas_, Jan 07 2018: (Start)

%e We explain why a(8) = 4. According to the theory of transforms by C. G. Bower, given in the weblink above, a(8) is the number of ways of arranging 6 indistinct unlabeled boxes (that may differ only in their size) as a necklace, on a circle, such that the total number of balls in all of them is 8. There are 4 ways for doing that on a circle: 311111, 221111, 212111, and 211211.

%e To translate these configurations of boxes into necklaces with 8 beads, 6 of them black and 2 of them white, we modify an idea given above by W. Lang. We replace each box that has m balls with a black bead followed by m-1 white beads. The four examples above become BWWBBBBB, BWBWBBBB, BWBBWBBB, and BWBBBWBB.

%e (End)

%t k = 6; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* _Robert A. Russell_, Sep 27 2004 *)

%Y Column k=6 of A047996.

%Y Cf. A004526, A007997, A008610, A008646.

%K nonn

%O 6,3

%A _Christian G. Bower_