A121981 Number of finite maximal bifix codes of degree n on a two-letter alphabet.

1, 1, 3, 73, 5056783

Offset

1,3

Comments

A bifix (sometimes biprefix) code is a set of nonempty words X such that no word of X is a proper prefix or a proper suffix of another. The degree of a finite maximal bifix code X is the maximal number of parses that a word can have with respect to X.

It is known that there are finitely many finite maximal bifix codes of each degree.

References

J. Berstel and D. Perrin, Theory of Codes, Academic Press, 1985, Chapter III.

Links

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

Example

On the alphabet {a,b}, for n=3 the a(3)=3 codes are:
{aaa,aab,aba,abb,baa,bab,bba,bbb},
{aaa,aaba,aabb,ab,baa,baba,babb,bba,bbb},
{aaa,aab,abaa,abab,abb,ba,bbaa,bbab,bbb}

Crossrefs

Sequence in context: A002667 A145675 A336873 * A337413 A337409 A215961

Adjacent sequences: A121978 A121979 A121980 * A121982 A121983 A121984

Keyword

nonn,hard

Author

Alessandro De Luca, Feb 09 2011

Status

approved