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

1, 0, 2, 3, 12, 26, 78, 195, 546, 1452, 4026, 11010, 30660, 85254, 239144, 672195, 1899120, 5379738, 15292914, 43581852, 124527988, 356594898, 1023295422, 2941952130, 8472886092, 24440956260, 70607383938

Offset: 1

Author

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 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,n_1=even.

Examples

			For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only 113 and 223 have an even number of both 1's and 2's. Thus a(3)=2.
		

References

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

Links

• E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• 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]
• F. Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
• M. Zabrocki, MATH5020 York University Course Website

Crossrefs

Cf. A006575; A027376; A133267; A136704.

Formula

a(1)=1; for n>1, if n=odd then a(n)= sum(mu(d)*3^(n/d))/(4n); d|n. If n=even, then a(n)= sum(mu(d)*3^(n/d))/n; d|n -(3/4)*sum(mu(d)*(3^(n/d)-1))/n; d|n, d odd.