|
Search: id:A136703
|
|
|
| A136703 |
|
Number of Lyndon words on {1,2,3} with an even number of 1's and an even number of 2's. |
|
+0
2
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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,n_1=even.
|
|
REFERENCES
|
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.
|
|
LINKS
|
F. Ruskey, Counting Necklaces
M. Zabrocki, MATH5020 York University Course Website
|
|
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.
|
|
EXAMPLE
|
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.
|
|
CROSSREFS
|
Cf. A006575; A027376; A133267; A136704.
Sequence in context: A099429 A049601 A016021 this_sequence A075269 A089414 A048085
Adjacent sequences: A136700 A136701 A136702 this_sequence A136704 A136705 A136706
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008
|
|
|
Search completed in 0.002 seconds
|
