|
|
A194850
|
|
Number of prefix normal words of length n.
|
|
4
|
|
|
2, 3, 5, 8, 14, 23, 41, 70, 125, 218, 395, 697, 1273, 2279, 4185, 7568, 13997, 25500, 47414, 87024, 162456, 299947, 562345, 1043212, 1962589, 3657530, 6900717, 12910042, 24427486, 45850670, 86970163, 163756708, 311283363, 587739559, 1119581278, 2119042830
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
A binary word of length n is prefix normal if for all 1 <= k <= n, no factor of length k has more a's than the prefix of length k. That is, abbabab is not prefix normal because aba has more a's than abb. - Zsuzsanna Liptak, Oct 12 2011
a(n) <= A062692(n): every prefix normal word is a pre-necklace, but the converse is not true, see the Fici/Lipták reference. - Joerg Arndt, Jul 20 2013
|
|
LINKS
|
G. Fici and Zs. Lipták, On Prefix Normal Words, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, On Collapsing Prefix Normal Words, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
|
|
EXAMPLE
|
For n=3: aaa, aab, abb, aba, bbb are all prefix normal words. - Zsuzsanna Liptak, Oct 12 2011
|
|
PROG
|
(Python)
from itertools import product
def is_prefix_normal(w):
for k in range(1, len(w)+1):
weight0 = w[:k].count("1")
for j in range(1, len(w)-k+1):
weightj = w[j:j+k].count("1")
if weightj > weight0: return False
return True
def a(n):
return sum(is_prefix_normal(w) for w in product("01", repeat=n))
|
|
CROSSREFS
|
Cf. A062692 (binary pre-necklaces).
See A238109 for a list of the prefix-normal words.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|