|
%I #54 Apr 30 2019 09:56:35
%S 1,6,15,70,315,1554,7735,39990,209790,1119720,6045837,32981550,
%T 181394535,1004668770,5597420295,31345665106,176319264240,
%U 995685849690,5642219252460,32071565263710,182807918979777
%N Number of aperiodic necklaces of n beads of 6 colors; dimensions of free Lie algebras.
%C From _Petros Hadjicostas_, Aug 31 2018: (Start)
%C 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)).
%C 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).
%C For the current sequence, k = 6.
%C (End)
%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.
%H Seiichi Manyama, <a href="/A032164/b032164.txt">Table of n, a(n) for n = 0..1289</a> (terms 0..200 from T. D. Noe)
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%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 G. Viennot, <a href="http://dx.doi.org/10.1007/BFb0067950">Algèbres de Lie Libres et Monoïdes Libres</a>, Lecture Notes in Mathematics 691, Springer Verlag 1978.
%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F "CHK" (necklace, identity, unlabeled) transform of 6, 0, 0, 0...
%F a(n) = Sum_{d|n} mu(d)*6^(n/d)/n, for n>0.
%F G.f.: k=6, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - _Herbert Kociemba_, Nov 25 2016
%t 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 *)
%t 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 *)
%o (PARI) a(n) = if (n==0, 1, sumdiv(n, d, moebius(d)*6^(n/d)/n)); \\ _Michel Marcus_, Dec 01 2015
%Y Column 6 of A074650.
%Y Cf. A001037, A001692 (5 colors).
%Y Cf. A054721.
%K nonn,easy,nice
%O 0,2
%A _Christian G. Bower_
|
