%I #31 Jan 29 2025 07:55:54
%S 2,1,4,8,24,56,156,400,1092,2928,8052,22080,61320,170664,478288,
%T 1344800,3798240,10760568,30585828,87166656,249055976,713197848,
%U 2046590844,5883926400,16945772184,48881973840,141214767876,408513980160,1183282368360,3431518388960
%N Number of Lyndon words on {1, 2, 3} with an even number of 1's.
%C A Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d)=sum L(n-d, n_1,..., n_(k-1)); n_1+...+n_(k-1)=d where L(n_0, n_1,...,n_(k-1))=(1/n)sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0=even. Alternatively, a(n)=(sum mu(d)*3^(n/d)/n; d|n) - (sum mu(d)*(3^(n/d)-1)/(2n); d|n, d odd).
%D M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
%H Alois P. Heinz, <a href="/A133267/b133267.txt">Table of n, a(n) for n = 1..650</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 Frank Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H Frank Ruskey and J. Sawada, <a href="http://dx.doi.org/10.1137/S0097539798344112">An Efficient Algorithm for Generating Necklaces with Fixed Density</a>, SIAM J. Computing, 29 (1999) 671-684.
%H Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Mike Zabrocki, <a href="http://garsia.math.yorku.ca/~zabrocki/math5020y0708/">Course website</a>
%F a(1)=2; for n>1, if n=2^k for some k, then a(n) = ((3^(n/2)-1)^2)/(2*n). Otherwise, if n is even then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-2*3^(n/(2*d)))/(2*n). If n is odd then a(n) = Sum_{d|n, d odd} mu(d)*(3^(n/d)-1)/(2*n).
%e For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only the first two and the last two have an even number of 1's. Thus a(3) = 4.
%p with(numtheory): a:= n-> add(mobius(d) *3^(n/d), d=divisors(n))/n -add(mobius(d) *(3^(n/d)-1), d=select(x-> irem(x, 2)=1, divisors(n)))/ (2*n): seq(a(n), n=1..30); # _Alois P. Heinz_, Jul 29 2011
%t a[n_] := DivisorSum[n, MoebiusMu[#]*(3^(n/#) - (1/2)*Boole[OddQ[#]]*(3^(n/#)-1))&]/n; Table[a[n], {n, 1, 30}] (* _Jean-François Alcover_, Mar 21 2017, after _Alois P. Heinz_ *)
%o (PARI) a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n))); \\ _Michel Marcus_, May 17 2018
%Y Cf. A006575, A027376.
%K nonn
%O 1,1
%A Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 03 2008