Mutual Borders and Overlaps.

A word is said to be bordered if it contains a non-empty proper prefix that is also a suffix. We can naturally extend this definition to pairs of non-empty words. A pair of words $(u,v)$ is said to be mutually bordered if there exists a word that is a non-empty proper prefix of $u$ and suffix of $v$ , and there exists a word that is a non-empty proper suffix of $u$ and prefix of $v$. In other words, $(u,v)$ is mutually bordered if $u$ overlaps $v$ and $v$ overlaps $u$. We give a recurrence for the number of mutually bordered pairs of words. Furthermore, we show that, asymptotically, there are $c\cdot k^{2n}$ mutually bordered words of length- $n$ over a $k$ -letter alphabet, where $c$ is a constant. Finally, we show that the expected shortest overlap between pairs of words is bounded above by a constant. [ABSTRACT FROM AUTHOR]