A032192 - OEIS

%I #84 Aug 06 2024 21:14:35

%S 1,1,4,12,30,66,132,246,429,715,1144,1768,2652,3876,5538,7752,10659,

%T 14421,19228,25300,32890,42288,53820,67860,84825,105183,129456,158224,

%U 192130,231880,278256,332112,394383,466089,548340

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

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

%C The g.f. is Z(C_7,x)/x^7, the 7-variate cycle index polynomial for the cyclic group C_7, with substitution x[i]->1/(1-x^i), i=1,...,7. Therefore by Polya enumeration a(n+7) is the number of cyclically inequivalent 7-necklaces whose 7 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_7,x) and the comment in A032191 on the equivalence of this problem with the one given in the 'Name' line. - _Wolfdieter Lang_, Feb 15 2005

%C From _Petros Hadjicostas_, Dec 08 2017: (Start)

%C For p prime, if a_p(n) is the number of necklaces with p black beads and n-p white beads, then (a_p(n): n>=1) = CIK[p](1, 1, 1, 1, ...). Since CIK[k](B(x)) = (1/k)*Sum_{d|k} phi(d)*B(x^d)^{k/d} with k = p and B(x) = x + x^2 + x^3 + ... = x/(1-x), we get Sum_{n>=1} a_p(n)*x^n = ((p-1)/(1 - x^p) + 1/(1 - x)^p)*x^p/p, which is _Herbert Kociemba_'s general formula for the g.f. when p is prime.

%C We immediately get a_p(n) = ((p-1)/p)*I(p|n) + (1/p)*C(n-1,p-1) = ((p-1)/p)*I(p|n) + (1/n)*C(n,p) = ceiling(C(n,p)/n), which is a generalization of the conjecture made by _N. J. A. Sloane_ and _Wolfdieter Lang_. (Here, I(condition) = 1 if the condition holds, and 0 otherwise. Also, as usual, for integers n and k, C(n,k) = 0 if 0 <= n < k.)

%C Since the sequence (a_p(n): n>=1) is column k = p of A047996(n,k) = T(n,k), we get from the documentation of the latter sequence that a_p(n) = T(n, p) = (1/n)*Sum_{d|gcd(n,p)} phi(d)*C(n/d, p/d), from which we get another proof of the formulae for a_p(n).

%C (End)

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

%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 pp. 5-6.

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

%H Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

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

%F Empirically this is ceiling(C(n, 7)/n). - _N. J. A. Sloane_

%F G.f.: x^7*(x^6 - 5*x^5 + 13*x^4 - 17*x^3 + 13*x^2 - 5*x + 1)/((x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)*(1 - x)^7). - Gael Linder (linder.gael(AT)wanadoo.fr), Jan 13 2005

%F G.f.: (6/(1 - x^7) + 1/(1 - x)^7)*x^7/7; in general, for a necklace with p black beads and p prime, the g.f. is ((p-1)/(1 - x^p) + 1/(1 - x)^p)*x^p/p. - _Herbert Kociemba_, Oct 15 2016

%F a(n) = ceiling(binomial(n, 7)/n) (conjecture by _Wolfdieter Lang_).

%F a(n) = (6/7)*I(7|n) + (1/7)*C(n-1,6) = (6/7)*I(7|n) + (1/n)*C(n,7), where I(condition) = 1 if the condition holds, and = 0 otherwise. - _Petros Hadjicostas_, Dec 08 2017

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

%t DeleteCases[CoefficientList[Series[x^7 (x^6 - 5 x^5 + 13 x^4 - 17 x^3 + 13 x^2 - 5 x + 1)/((x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) (1 - x)^7), {x, 0, 41}], x], 0] (* _Michael De Vlieger_, Oct 10 2016 *)

%Y Column k=7 of A047996.

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

%K nonn

%O 7,3

%A _Christian G. Bower_