This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

(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: A254821 A192953 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 23 09:29 EST 2017. Contains 295115 sequences.