A133267 Number of Lyndon words on {1, 2, 3} with an even number of 1's.

2, 1, 4, 8, 24, 56, 156, 400, 1092, 2928, 8052, 22080, 61320, 170664, 478288, 1344800, 3798240, 10760568, 30585828, 87166656, 249055976, 713197848, 2046590844, 5883926400, 16945772184, 48881973840, 141214767876, 408513980160, 1183282368360, 3431518388960

Offset: 1

Author

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 03 2008

Keywords

• nonn

Comments

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

Examples

			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.
		

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..650
• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Frank Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Mike Zabrocki, Course website

Crossrefs

Cf. A006575, A027376.

Programs

Maple

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

Mathematica

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

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

Formula

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