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

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

Offset: 1

Author

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

Keywords

• nonn

Comments

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.

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(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 = odd.

Examples

			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.
		

References

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

Links

• Amiram Eldar, Table of n, a(n) for n = 1..1000
• E. N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
• Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
• Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999), 671-684.
• Mike Zabrocki, MATH5020 York University Course Website.

Crossrefs

Cf. A006575, A027376, A133267, A136703.

Bisections: A253076, A253077.

Programs

Mathematica

a[1] = 0;
a[n_] := If[OddQ[n], Sum[MoebiusMu[d] * 3^(n/d), {d, Divisors[n]}], Sum[Boole[OddQ[d]] MoebiusMu[d] * (3^(n/d)-1), {d, Divisors[n]}]]/(4n);
Array[a, 27] (* Jean-François Alcover, Aug 26 2019 *)

PARI

a(n) = if (n==1, 0, if (n % 2, sumdiv(n, d, moebius(d)*3^(n/d))/(4*n), sumdiv(n, d, if (d%2, moebius(d)*(3^(n/d)-1)))/(4*n))); \\ Michel Marcus, Aug 26 2019

Formula

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