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,3

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.

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.

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).

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.

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 *)

Prog

(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

Crossrefs

Cf. A006575, A027376, A133267, A136703.

Bisections: A253076, A253077.

Sequence in context: A188378 A145267 A103287 * A120895 A101785 A363306

Adjacent sequences: A136701 A136702 A136703 * A136705 A136706 A136707

Keyword

nonn

Author

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

Status

approved