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.