login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A133267 Number of Lyndon words on {1, 2, 3} with an even number of 1's. 5
2, 1, 4, 8, 24, 56, 156, 400, 1092, 2928, 8052, 22080, 61320, 170664, 478288, 1344800, 3798240, 10760568, 30585828, 87166656, 249055976, 713197848, 2046590844, 5883926400, 16945772184, 48881973840, 141214767876, 408513980160 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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=even. Alternatively, a(n)=(sum mu(d)*3^(n/d)/n; d|n) - (sum mu(d)*(3^(n/d)-1)/(2n); d|n, d odd).

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..650

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

F. Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

M. Zabrocki, Course website

FORMULA

a(1)=2; for n>1, if n=2^k for some k, then a(n)=((3^(n/2)-1)^2)/(2n). Otherwise, if n=even then a(n)=sum mu(d)*(3^(n/d)-2*3^(n/(2d))/(2n); d|n, d odd. If n=odd then a(n)=sum mu(d)*(3^(n/d)-1)/(2n); d|n, d odd.

EXAMPLE

For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only the first two and the last two have an even number of 1's. Thus a(3) = 4.

MAPLE

with(numtheory): a:= n-> add(mobius(d) *3^(n/d), d=divisors(n))/n -add(mobius(d) *(3^(n/d)-1), d=select(x-> irem(x, 2)=1, divisors(n)))/ (2*n): seq(a(n), n=1..30);  # Alois P. Heinz, Jul 29 2011

MATHEMATICA

a[n_] := DivisorSum[n, MoebiusMu[#]*(3^(n/#) - (1/2)*Boole[OddQ[#]]*(3^(n/#)-1))&]/n; Table[a[n], {n, 1, 30}] (* Jean-Fran├žois Alcover, Mar 21 2017, after Alois P. Heinz *)

PROG

(PARI) a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n))); \\ Michel Marcus, May 17 2018

CROSSREFS

Cf. A006575, A027376.

Sequence in context: A113820 A319479 A303632 * A145864 A306392 A182739

Adjacent sequences:  A133264 A133265 A133266 * A133268 A133269 A133270

KEYWORD

nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 18 21:25 EDT 2019. Contains 325144 sequences. (Running on oeis4.)