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

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.

Links

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

Example

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.

Sequence in context: A359366 A226303 A117781 * A288660 A212440 A066861

Adjacent sequences: A075097 A075098 A075099 * A075101 A075102 A075103

Keyword

hard,more,nonn

Author

Colin Mallows, Aug 31 2002

Extensions

Edited by Andrey Zabolotskiy, Nov 08 2024

Status

approved