A correlation is a binary vector that encodes all possible positions of overlaps of two words, where an overlap for an ordered pair of words (u, v) occurs if a suffix of u matches a prefix of v. As multiple pairs can have the same correlation, it is relevant to count how many pairs of words share the same correlation, depending on the alphabet size and word length n. We exhibit recurrences to compute the number of such pairs – which is termed population size – for any correlation; for this, we exploit a relationship between overlaps of two words and self-overlap of one word. This theorem allows us to compute the number of pairs with the longest overlap of a given length, solving two open questions Gabric raised in 2022. Finally, we also provide bounds for the asymptotic population ratio of any correlation. Given the importance of word overlaps in areas like combinatorics on words, bioinformatics, and digital communication, our results may ease analyses of algorithms for string processing, code design, or genome assembly.
