Lenormand concatenated words on alphabet (x,y)

[reismann at free.fr]

Dear Seqfans and Eric

> 0,1,10,100,101,1000,1001,1011,10000,10001,10010,10011,10100,10110,10111,100000
>
> ... which is in base 10:
>
> 0 1 2 4 5 8 9 11 16 17 18 19 20 22 23 32 ...

with the strongest weights to the left.

> « Enumération et factorisation des mots sur (x,y)
>   comme fonction ordonnée des mots de S:
>
>   (dans S, x est le seul mot dont la première lettre
>   est x, aucun mot ne commence par yy, par contre tout
>   mot de la forme yxi convient, et pour tout mot m de S
>   distinct de x et y, my convient....)

"Enumeration and factorization of the words on (x, y) as ordinated function of
the words of S : in S, (x) is the only word which the first letter is x, no word
begins by (yy), any word of the form (yxi) agrees, and for any word m of S
different of x and y, (my) agrees.

(x) (y)
x.x x.y (yx) y.y
x.x.x x.x.y x.yx x.y.y (yxx) (yxy) y.yx y.y.y
x.x.x.x x.x.x.y x.x.yx x.x.y.y x.yxx x.yxy x.y.yx x.y.y.y (yxxx) (yxxy) yx.yx
(yxyy) y.yxx
y.yxy y.y.yx y.y.y.y ...

Best,

Rémi



If I understand correctly, yxyxx should not be on the list as
yx precedes yxx.

The number of words of length n should be the same as the number of
Lyndon words of length 2
http://www.research.att.com/~njas/sequences/A001037
owing to the fact that if you perform "ordinated concatenation" to the
words on the list, you get all binary words, hence the number of words
is given by the inverse Euler transform of 2^n which gives the Lyndon
words. The actual position of the bits is different than that of a
Lyndon word, thus giving a new sequence.

As far as being of interest. Sequences generated from a problem in a math
text are usually of interest. There should be a reference to A001037
and a comment about Lyndon words.

Christian

------ Original Message ------

> 
> Hello SeqFan,
> 
> This is « Exercice 14 », there:
> http://www.ai.univ-paris8.fr/~lenormand/chapitre1/1.1_Prolegomenes.pdf
> 
> My translation:
> 
> --------------------------------------------------
> (...)
> 
> No word of this sequence S of words on alphabet (x,y)
> is produced by ordinated concatenation of the words 
> appearing before:
> 
> x y yx yxx yxy yxxx yxxy yxyy yxxxx yxxxy yxxyx yxxyy yxyxx yxyyx yxyyy
yxxxxx ...
> 
> .. doing x=0 and y=1 gives:
> 
>
0,1,10,100,101,1000,1001,1011,10000,10001,10010,10011,10100,10110,10111,100000
> 
> .. which is in base 10:
> 
> 0 1 2 4 5 8 9 11 16 17 18 19 20 22 23 32 ...
> 
> (...)
> --------------------------------------------------
> .. This seq. is not in the OEIS, if I'm not wrong.
> 
> My french is not good enough to understand how this 
> seq. is produced, though :
> 
> --------------------------------------------------
> (...)
> 
> « Enumération et factorisation des mots sur (x,y) 
>   comme fonction ordonnée des mots de S:
> 
>   (dans S, x est le seul mot dont la première lettre
>   est x, aucun mot ne commence par yy, par contre tout
>   mot de la forme yxi convient, et pour tout mot m de S
>   distinct de x et y, my convient....)
> 
> x y
> x.x x.y yx y.y
> x.x.x x.x.y x.yx x.y.y yxx yxy y.yx y.y.y
> x.x.x.x x.x.x.y x.x.yx x.x.y.y x.yxx x.yxy x.y.yx x.y.y.y yxxx yxxy yx.yx
yxyy y.yxx
> y.yxy y.y.yx y.y.y.y ... »
> 
> (...)
> --------------------------------------------------
> Is this of interest ?
> 
> Best,
> É.
> 
> 







Dear Seqfans,   Some robot has been sending me dozens
of sequences every day, which are really ads for certain
drugs.

So I made some changes to the "Submit" program to foil this.
Please let me know at once if I have messed it up.

Neil

PS  Feel free to send me test sequences or test comments
(just say "ignore this")