1,1

A Lyndon word is the aperiodic necklace representative which is lexicographically smallest 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).

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

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

F. Ruskey and J. Sawada, "An Efficient Algorithm for Generating Necklaces with Fixed Density", SIAM J. Computing, 29 (1999) 671-684.

F. Ruskey, Counting Necklaces

M. Zabrocki, Course website

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

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.

Cf. A006575; A027376.

Sequence in context: A156817 A008301 A113820 this_sequence A145864 A076014 A120458

Adjacent sequences: A133264 A133265 A133266 this_sequence A133268 A133269 A133270

nonn

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