A032194 Number of necklaces with 9 black beads and n-9 white beads.

1, 1, 5, 19, 55, 143, 335, 715, 1430, 2704, 4862, 8398, 14000, 22610, 35530, 54484, 81719, 120175, 173593, 246675, 345345, 476913, 650325, 876525, 1168710, 1542684, 2017356, 2615104, 3362260, 4289780, 5433736, 6835972

Offset: 9

Author

Christian G. Bower

Keywords

• nonn

Comments

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

Links

• Christian G. Bower, Transforms (2)
• David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See p. 19.
• 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,22,-27,36,-42,36,-27,23,-21,21,-23,27,-36,42,-36,27,-22,15,-6,1).

Crossrefs

Column k=9 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193.

Programs

Mathematica

k = 9; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)

Formula

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

G.f.: (x^9)*(1-5*x+14*x^2-18*x^3+21*x^4-21*x^5+25*x^6 -21*x^7 +21*x^8 -18*x^9 +14*x^10 -5*x^11 +x^12) / ((1-x)^6*(1-x^3)^2*(1-x^9)).

G.f.: (1/9)*x^9*(1/(1-x)^9+2/(1-x^3)^3+6/(1-x^9)^1). - Herbert Kociemba, Oct 22 2016