A075100 Number of words of length strictly between 1 and n that are needed on the way to computing all words of length n in the free monoid with two generators.

0, 0, 3, 4, 10, 11

Offset: 1

Author

Colin Mallows, Aug 31 2002

Keywords

• hard
• more
• nonn

Comments

I believe a(2n) = a(n) + 2^n. I think a(7) = 28.

Benoit Jubin (Jan 24 2009) suggests replacing "monoid" in the definition by "semigroup" and remarks that it makes sense to introduce a new sequence that includes words of length 1 in the count.

Examples

			a(3) = 3 because we need only xx, xy, yy to generate each of xxx, xxy, xyx, yxx, xyy, yxy, yyx, yyy.
		

Crossrefs

Cf. A075099, A003313, A124677.

Extensions

Edited by Andrey Zabolotskiy, Nov 08 2024