

A032193


Number of necklaces with 8 black beads and n8 white beads.


4



1, 1, 5, 15, 43, 99, 217, 429, 810, 1430, 2438, 3978, 6310, 9690, 14550, 21318, 30667, 43263, 60115, 82225, 111041, 148005, 195143, 254475, 328756, 420732, 534076, 672452, 840652, 1043460, 1287036, 1577532, 1922741
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

8,3


COMMENTS

The g.f. is Z(C_8,x)/x^8, the 8variate cycle index polynomial for the cyclic group C_8, with substitution x[i]>1/(1x^i), i=1,...,8. Therefore by Polya enumeration a(n+8) is the number of cyclically inequivalent 8necklaces whose 8 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_8,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
From Petros Hadjicostas, Aug 31 2018: (Start)
The CIK[k] transform of sequence (c(n): n>=1) has generating function A_k(x) = (1/k)*Sum_{dk} phi(d)*C(x^d)^{k/d}, where C(x) = Sum_{n>=1} c(n)*x^n is the g.f. of (c(n): n>=1).
When c(n) = 1 for all n >= 1, we get C(x) = x/(1x) and A_k(x) = (x^k/k)*Sum_{dk} phi(d)*(1x^d)^{k/d}, which is the g.f. of the number a_k(n) of necklaces of n beads of 2 colors with k of them black and nk of them white.
Using Taylor expansions, we can easily prove that a_k(n) = (1/k)*Sum_{dgcd(n,k)} phi(d)*binomial(n/d  1, k/d  1) = (1/n)*Sum_{dgcd(n,k)} phi(d)*binomial(n/d, k/d), which is Robert A. Russell's formula in the Mathematica code below.
For this sequence k = 8, and thus we get the formulae below.
(End)


LINKS

Table of n, a(n) for n=8..40.
C. G. Bower, Transforms (2)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces


FORMULA

"CIK[ 8 ]" (necklace, indistinct, unlabeled, 8 parts) transform of 1, 1, 1, 1...
G.f.: (x^8)*(13*x+5*x^2+3*x^34*x^4+4*x^5+6*x^64*x^7+7*x^8x^9+x^10+x^11)/((1x)^4*(1x^2)^2*(1x^4)*(1x^8)).
G.f.: 1/8*x^8*(1/(1x)^8+1/(1x^2)^4+2/(1x^4)^2+4/(1x^8)^1).  Herbert Kociemba, Oct 22 2016
a(n) = (1/8)*Sum_{dgcd(n,8)} phi(d)*binomial(n/d  1, 8/d  1) = (1/n)*Sum_{dgcd(n,8)} phi(d)*binomial(n/d, 8/d).  Petros Hadjicostas, Aug 31 2018


MATHEMATICA

k = 8; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)
CoefficientList[Series[1/8*(1/(1  x)^8 + 1/(1  x^2)^4 + 2/(1  x^4)^2 + 4/(1  x^8)^1), {x, 0, 30}], x] (* Stefano Spezia, Sep 01 2018 *)


CROSSREFS

Column k=8 of A047996.
Cf. A004526, A005514, A007997, A008610, A008646, A032191, A032192.
Sequence in context: A053731 A111295 A200760 * A178965 A005665 A025471
Adjacent sequences: A032190 A032191 A032192 * A032194 A032195 A032196


KEYWORD

nonn


AUTHOR

Christian G. Bower


STATUS

approved



