On the Appearance of Seeds In Words

Abstract

A seed of a word $x$ is a cover of a superword of $x$. In this paper, we study the frequency of appearance of seeds in words. We give bounds for the average number of seeds in a word and we investigate the maximum number of distinct seeds that can appear in a word. More precisely, we prove that a word has $O(n)$ seeds on average and that the maximum number of distinct seeds in a word is between $\frac{1}{6}(n^2)+o(n^2)$ and $\frac{1}{4}(n^2)+o(n^2)$, and we reveal some properties of an extremal word for the last case.