[seqfan] A certain semigroup

David Newman davidsnewman at gmail.com
Tue Nov 18 18:36:54 CET 2008

I have the following counting problem concerning a semigroup discussed by

Suppose words are made up from an alphabet of three letters, a, b, and c,
and that X,Y, and Z are three such words (possibly empty).
      Two words are considered to be equivalent if they can be expressed as
XYZYX and YXZXY.  For example, abba and baab are equivalent words, and abcba
and bacab are equivalent words.
     If two words are equivalent, say U=V, then it is also true that XU=XV,
and that UX=VX.  For example, since it is true by the previous paragraph
that abba=baab, it is also true that
aabba=abaab and abbaa=baaba.

Question:  How many non-equivalent words are there with two a's, two b''s,
and n c's ?

The values which I have thus far are

n         a(n)

4          5
5          27
6          67
7          127
8          207
9          309

More information about the SeqFan mailing list