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

1, 1, 4, 12, 30, 66, 132, 246, 429, 715, 1144, 1768, 2652, 3876, 5538, 7752, 10659, 14421, 19228, 25300, 32890, 42288, 53820, 67860, 84825, 105183, 129456, 158224, 192130, 231880, 278256, 332112, 394383, 466089, 548340

Offset: 7

Author

Christian G. Bower

Keywords

• nonn

Comments

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

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

From Petros Hadjicostas, Dec 08 2017: (Start)

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.

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.)

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).

(End)

Links

• C. G. Bower, Transforms (2)
• David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See p. 19.
• Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions, arXiv:2403.20148 [math.CO], 2024. See pp. 5-6.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Index entries for sequences related to necklaces
• Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1,1,-6,15,-20,15,-6,1).

Crossrefs

Column k=7 of A047996.

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

Programs

Mathematica

k = 7; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)
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 *)

Formula

Empirically this is ceiling(C(n, 7)/n). - N. J. A. Sloane

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

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

a(n) = ceiling(binomial(n, 7)/n) (conjecture by Wolfdieter Lang).

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