

A136704


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


3



0, 1, 2, 5, 12, 30, 78, 205, 546, 1476, 4026, 11070, 30660, 85410, 239144, 672605, 1899120, 5380830, 15292914, 43584804, 124527988, 356602950, 1023295422, 2941974270, 8472886092, 24441017580, 70607383938
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

1) This sequence is also the number of Lyndon words on {1,2,3} with an even number of 1's and an odd number of 2's except that a(1)=1 in this case. 2) Also, 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(nd, n_1,..., n_(k1)); n_1+...+n_(k1)=d where L(n_0, n_1,...,n_(k1))=(1/n)sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k1)/j)!)]; jgcd(n_0, n_1,...,n_(k1)). For this sequence, sum over n_0, n_1=odd.


REFERENCES

M. Lothaire, Combinatorics on Words, AddisonWesley, Reading, MA, 1983.


LINKS

Table of n, a(n) for n=1..27.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657665.
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) 671684.
M. Zabrocki, MATH5020 York University Course Website


FORMULA

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


EXAMPLE

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


CROSSREFS

Cf. A006575; A027376; A133267; A136703.
Bisections: A253076, A253077.
Sequence in context: A188378 A145267 A103287 * A120895 A101785 A003089
Adjacent sequences: A136701 A136702 A136703 * A136705 A136706 A136707


KEYWORD

nonn


AUTHOR

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


STATUS

approved



