A032196 Number of necklaces with 11 black beads and n-11 white beads.

1, 1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32066, 58786, 104006, 178296, 297160, 482885, 766935, 1193010, 1820910, 2731365, 4032015, 5864750, 8414640, 11920740, 16689036, 23107896, 31666376, 42975796

Offset: 11

Author

Christian G. Bower

Keywords

• nonn

Comments

The g.f. is Z(C_11,x)/x^11, the 11-variate cycle index polynomial for the cyclic group C_11, with substitution x[i]->1/(1-x^i), i=1..11. By Polya enumeration, a(n+11) is the number of cyclically inequivalent 11-necklaces whose 11 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_11,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

• 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
• Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1,1,-10,45,-120,210,-252,210,-120,45,-10,1).

Crossrefs

Column k=11 of A047996.

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

Programs

Mathematica

k = 11; 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^11) (1 - 9 x + 41 x^2 - 109 x^3 + 191 x^4 - 229 x^5 + 191 x^6 - 109 x^7 + 41 x^8 - 9 x^9 + x^10)/((1 - x)^10 (1 - x^11)), {x, 0, 39}], x], 0] (* Michael De Vlieger, Oct 10 2016 *)

Formula

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

G.f.: (x^11) * (1 - 9*x + 41*x^2 - 109*x^3 + 191*x^4 - 229*x^5 + 191*x^6 - 109*x^7 + 41*x^8 - 9*x^9 + x^10) / ((1-x)^10 * (1-x^11)).

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

From Herbert Kociemba, Oct 11 2016: (Start)

This conjecture indeed is true.

Sketch of proof:

There are binomial(n,11) ways to place the 11 black beads in the necklace with n beads. If n is not divisible by 11 there are no necklaces with a rotational symmetry. So exactly n necklaces are equivalent up to rotation and there are binomial(n,11)/n = ceiling(binomial(n,11)/n) equivalence classes.

If n is divisible by 11 the only way to get a necklace with rotational symmetry is to space out the 11 black beads evenly. There are n/11 ways to do this and all ways are equivalent up to rotation. So there are binomial(n,11) - n/11 unsymmetric necklaces which give binomial(n,11)/n - 1/11 equivalence classes. If we add the single symmetric equivalence class we get Binomial(n,11)/n - 1/11 + 1 which also is ceiling(binomial(n,11)/n). (End)

G.f.: (10/(1 - x^11) + 1/(1 - x)^11)*x^11/11. - Herbert Kociemba, Oct 16 2016