[seqfan] Re: A certain semigroup

[Max Alekseyev]

David,

Rephrasing your definition, two words S and T are "equivalent" if they
are of the form S=UXYZYXV and T=UYXZXYV for some (possibly empty)
words U,V,X,Y,Z.
However, there is a problem with this definition that can be
illustrated with the following three words:

S1 = abbaccb
S2 = baabccb
S3 = baacbbc

It is clear that S1 is "equivalent" S2 (taking U=Z=empty, X=a, Y=b,
V=ccb) and S2 is "equivalent" to S3 (taking U=baa, X=b, Y=c,
V=Z=empty). But S1 is NOT "equivalent" to S3! Hence, this
"equivalence" is not real equivalence relation as it does not obey
transitivity.

With this respect, it is not clear what you count. There may exists
multiple maximum pairwise non-"equivalent" sets of words of different
cardinality. Are you interested in a set of the maximum cardinality?

Regards,
Max


On Tue, Nov 18, 2008 at 9:36 AM, David Newman <davidsnewman at gmail.com> wrote:
> I have the following counting problem concerning a semigroup discussed by
> Shneerson.
>
>
> 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
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>