A121981 - OEIS

%I #15 Mar 31 2012 10:25:30

%S 1,1,3,73,5056783

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

%C 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.

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

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

%e On the alphabet {a,b}, for n=3 the a(3)=3 codes are:

%e {aaa,aab,aba,abb,baa,bab,bba,bbb},

%e {aaa,aaba,aabb,ab,baa,baba,babb,bba,bbb},

%e {aaa,aab,abaa,abab,abb,ba,bbaa,bbab,bbb}

%K nonn,hard

%O 1,3

%A _Alessandro De Luca_, Feb 09 2011