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,3

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

Table of n, a(n) for n=9..40.

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

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

a(n) = n^8/362880 - n^7/10080 + 13/8640*n^6 - n^5/80 + 1069/17280*n^4 - 89/480*n^3 + O(n^2). - Charles R Greathouse IV, May 26 2026

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

Prog

(PARI) a(n)=n^8/362880-n^7/10080+13/8640*n^6-n^5/80+1069/17280*n^4-89/480*n^3+10217/30240*n^2-347/840*n+((n%3==0)-1)*(n^2-9*n)/81+gcd(n, 9)/9 \\ Charles R Greathouse IV, May 27 2026

Crossrefs

Column k=9 of A047996.

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

Sequence in context: A060100 A053733 A381351 * A024532 A036421 A295776

Adjacent sequences: A032191 A032192 A032193 * A032195 A032196 A032197

Keyword

nonn,easy

Author

Christian G. Bower

Status

approved