|
%I #11 Apr 30 2019 08:31:29
%S 1,0,2,3,12,26,78,195,546,1452,4026,11010,30660,85254,239144,672195,
%T 1899120,5379738,15292914,43581852,124527988,356594898,1023295422,
%U 2941952130,8472886092,24440956260,70607383938
%N Number of Lyndon words on {1,2,3} with an even number of 1's and an even number of 2's.
%C 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.
%D M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
%H E. N. Gilbert and J. Riordan, <a href="http://projecteuclid.org/euclid.ijm/1255631587">Symmetry types of periodic sequences</a>, Illinois J. Math., 5 (1961), 657-665.
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H F. Ruskey and J. Sawada, <a href="http://dx.doi.org/10.1137/S0097539798344112">An Efficient Algorithm for Generating Necklaces with Fixed Density</a>, SIAM J. Computing, 29 (1999) 671-684.
%H M. Zabrocki, <a href="http://garsia.math.yorku.ca/~zabrocki/math5020y0708/">MATH5020 York University Course Website</a>
%F 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.
%e 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.
%Y Cf. A006575; A027376; A133267; A136704.
%K nonn
%O 1,3
%A Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008
|
