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)

68R15 Combinatorics on words
finite alphabet
Full Text: DOI