The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A124677 Minimal total number of multiplications by single letters needed to generate all words of length n in the free monoid on two generators. 2
0, 2, 6, 13, 27 (list; graph; refs; listen; history; text; internal format)



Table of n, a(n) for n=0..4.


Form a tree with the empty word 0 as the root. Each node has potentially 4 children, corresponding to premultiplication by x or y and postmultiplication by x and y.

Layers 0 through 3 of the tree are as follows (the edges, which just join one layer to the next, have been omitted):




xxx xxy xyx yxx xyy yxy yyx yyy

a(n) is the minimal number of edges in a subtree that includes the root and all 2^n nodes at level n.

a(3) = 13 because each of xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy can be obtained in one step from xx,xy,yy; that is, we don't need yx. The corresponding subtree has 2 + 3 + 8 = 13 edges.

a(4) = 27 because one computes successively: 0, x,y, xx,xy,yy, xxx,xyx,xxy,yxy,yyx,yyy and then all 16 words of length 4.


See A075099, A075100 for a different way of counting multiplications. Here we only grow the words one letter at a time.

Sequence in context: A192953 A353232 A275970 * A034465 A182614 A288901

Adjacent sequences:  A124674 A124675 A124676 * A124678 A124679 A124680




N. J. A. Sloane, Dec 25 2006


Definition clarified by Benoit Jubin, Jan 24 2009



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 02:05 EDT 2022. Contains 356986 sequences. (Running on oeis4.)