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,2

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.

Links

Table of n, a(n) for n=1..6.

Example

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).

Sequence in context: A008174 A363604 A008262 * A240784 A345434 A297961

Adjacent sequences: A075096 A075097 A075098 * A075100 A075101 A075102

Keyword

hard,more,nonn

Author

Colin Mallows, Aug 31 2002

Status

approved