# zbMATH — the first resource for mathematics

On a conjecture by Eriksson concerning overlap in strings. (English) Zbl 0946.68111
Summary: Consider a finite alphabet $$\Omega$$ and strings consisting of elements from $$\Omega$$. For a given string $$w$$, let $$\text{cor}(w)$$ denote the autocorrelation, which can be seen as a measure of the amount of overlap in $$w$$. Furthermore, let $$a_w(n)$$ be the number of strings of length $$n$$ that do not contain $$w$$ as a substring. K. Eriksson [Comb. Probab. Comput. 6, No. 1, 45-48 (1997; Zbl 0865.68097)] stated the following conjecture: if $$\text{cor}(w)> \text{cor}(w')$$, then $$a_w(n)> a_{w'}(n)$$ from the first $$n$$ where equality no longer holds. We prove that this is true if $$|\Omega|\geq 3$$, by giving a lower bound for $$a_w(n)- a_{w'}(n)$$.
Reviewer: Reviewer (Berlin)

##### MSC:
 68R15 Combinatorics on words
finite alphabet
Full Text: