A075099 Minimal total number of multiplications needed to generate all words of length n in the free monoid on two generators.

0, 4, 11, 20, 42, 75

Offset: 1

Author

Colin Mallows, Aug 31 2002

Keywords

• hard
• more
• nonn

Comments

Benoit Jubin (Jan 24 2009) suggests replacing "monoid" in the definition by "semigroup".

I believe a(2n) = a(n) + 2^(2n). I guess a(7) = 156.

Examples

			a(3)=11 because each of xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy can be obtained in one step from xx,xy,yy and it takes three multiplications to produce xx, xy, yy.
		

Crossrefs

Cf. A075100, A124677 (another version).