On the Size of the Neighborhoods of a Word

The $d$-neighborhood of a word $w$ in the Levenshtein distance is the set of all words at distance at most $d$ from $w$. Generating the neighborhood of a word $w$, or related sets of words such as the condensed neighborhood or the super-condensed neighborhood has applications in the design of approximate pattern matching algorithms. It follows that bounds on the maximum size of the neighborhood for the words of a given length can be used in the complexity analysis of such approximate pattern matching algorithms. In this note, we present exact formulas for the sizes of the condensed and super condensed neighborhoods of unary words, establish a novel upper bound and prove a conjectured upper bound for the size of the condensed neighborhoods of an arbitrary word.