A032193 - OEIS

%I #58 Apr 30 2019 09:57:11

%S 1,1,5,15,43,99,217,429,810,1430,2438,3978,6310,9690,14550,21318,

%T 30667,43263,60115,82225,111041,148005,195143,254475,328756,420732,

%U 534076,672452,840652,1043460,1287036,1577532,1922741

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

%C The g.f. is Z(C_8,x)/x^8, the 8-variate cycle index polynomial for the cyclic group C_8, with substitution x[i]->1/(1-x^i), i=1,...,8. Therefore by Polya enumeration a(n+8) is the number of cyclically inequivalent 8-necklaces 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

%C From _Petros Hadjicostas_, Aug 31 2018: (Start)

%C The CIK[k] transform of sequence (c(n): n>=1) has generating function A_k(x) = (1/k)*Sum_{d|k} 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).

%C When c(n) = 1 for all n >= 1, we get C(x) = x/(1-x) and A_k(x) = (x^k/k)*Sum_{d|k} phi(d)*(1-x^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 n-k of them white.

%C Using Taylor expansions, we can easily prove that a_k(n) = (1/k)*Sum_{d|gcd(n,k)} phi(d)*binomial(n/d - 1, k/d - 1) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*binomial(n/d, k/d), which is Robert A. Russell's formula in the Mathematica code below.

%C For this sequence k = 8, and thus we get the formulae below.

%C (End)

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

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

%H F. 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 "CIK[ 8 ]" (necklace, indistinct, unlabeled, 8 parts) transform of 1, 1, 1, 1...

%F G.f.: (x^8)*(1-3*x+5*x^2+3*x^3-4*x^4+4*x^5+6*x^6-4*x^7+7*x^8-x^9+x^10+x^11)/((1-x)^4*(1-x^2)^2*(1-x^4)*(1-x^8)).

%F G.f.: 1/8*x^8*(1/(1-x)^8+1/(1-x^2)^4+2/(1-x^4)^2+4/(1-x^8)^1). - _Herbert Kociemba_, Oct 22 2016

%F a(n) = (1/8)*Sum_{d|gcd(n,8)} phi(d)*binomial(n/d - 1, 8/d - 1) = (1/n)*Sum_{d|gcd(n,8)} phi(d)*binomial(n/d, 8/d). - _Petros Hadjicostas_, Aug 31 2018

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

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

%Y Column k=8 of A047996.

%Y Cf. A004526, A005514, A007997, A008610, A008646, A032191, A032192.

%K nonn

%O 8,3

%A _Christian G. Bower_