A032164 Number of aperiodic necklaces of n beads of 6 colors; dimensions of free Lie algebras.

1, 6, 15, 70, 315, 1554, 7735, 39990, 209790, 1119720, 6045837, 32981550, 181394535, 1004668770, 5597420295, 31345665106, 176319264240, 995685849690, 5642219252460, 32071565263710, 182807918979777

Offset: 0

Author

Christian G. Bower

Keywords

• nonn
• easy
• nice

Comments

From Petros Hadjicostas, Aug 31 2018: (Start)

For each m >= 1, the CHK[m] transform of sequence (c(n): n>=1) has generating function B_m(x) = (1/m)*Sum_{d|m} mu(d)*C(x^d)^{m/d}, where C(x) = Sum_{n>=1} c(n)*x^n is the g.f. of (c(n): n >= 1). As a result, the CHK transform of sequence (c(n): n >= 1) has generating function B(x) = Sum_{m >= 1} B_m(x) = -Sum_{n >= 1} (mu(n)/n)*log(1 - C(x^n)).

For n, k >= 1, let a_k(n) = number of aperiodic necklaces of n beads of k colors. We then have (a_k(n): n >= 1) = CHK(c_k(n): n >= 1), where c_k(1) = k and c_k(n) = 0 for all n >= 2, with g.f. C_k(x) = Sum_{n >= 1} c_k(n)*x^n = k*x. The g.f. of (a_k(n): n >= 1) is A_k(x) = Sum_{n >= 1} a_k(n)*x^n = -Sum_{n >= 1} (mu(n)/n)*log(1-k*x^n), which is Herbert Kociemba's general formula below (except for the initial term a_k(0) = 1).

For the current sequence, k = 6.

(End)

References

• M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1289 (terms 0..200 from T. D. Noe)
• C. G. Bower, Transforms (2)
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
• 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]
• G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
• Index entries for sequences related to Lyndon words

Crossrefs

Column 6 of A074650.

Cf. A001037, A001692 (5 colors).

Cf. A054721.

Programs

Mathematica

f[d_] := MoebiusMu[d]*6^(n/d)/n; a[n_] := Total[f /@ Divisors[n]]; a[0] = 1; Table[a[n], {n, 0, 20}](* Jean-François Alcover, Nov 07 2011 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,6],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

PARI

a(n) = if (n==0, 1, sumdiv(n, d, moebius(d)*6^(n/d)/n)); \\ Michel Marcus, Dec 01 2015

Formula

"CHK" (necklace, identity, unlabeled) transform of 6, 0, 0, 0...

a(n) = Sum_{d|n} mu(d)*6^(n/d)/n, for n>0.

G.f.: k=6, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016