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

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

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

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

Prog

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

Crossrefs

Column 6 of A074650.

Cf. A001037, A001692 (5 colors).

Cf. A054721.

Sequence in context: A318555 A359923 A035077 * A177122 A108540 A232170

Adjacent sequences: A032161 A032162 A032163 * A032165 A032166 A032167

Keyword

nonn,easy,nice

Author

Christian G. Bower

Status

approved