Number of strings at given edit distance

I would like to know the number of strings at edit distance $$n$$ of a string $$s$$.

I guess this is textbook knowledge... but I cannot find the textbook in question.

More formally, I have an alphabet $$\Sigma$$ (in my case, $$|\Sigma| = 4$$), and I consider all the words in $$\Sigma^*$$. I use the edit distance $$d$$. I am looking for the number of words at distance $$n$$ of a word $$w \in \Sigma^*$$. Namely,

$$f_1(w, n) = \lvert \{ w' \in \Sigma^*: d(w, w') = n \} \rvert$$

I need the maximum size, considering all the words of a given length. Namely:

$$f_2(s, n) = \max_{w,\ |w| = s}(f_1(w, n))$$

In practice, I have to compute a table of $$f_2$$ with $$s \in [0, 100]$$, and $$n \in [0, 5]$$, so I can compute $$f_2$$ recursively.

I tried to read the original Levenshtein paper, but it seems to deal with binary alphabets only.

What I had in mind, is that $$f_2(s, n)$$ can be computed with $$f_2(s, n-1)$$, and adding an error: insertion, deletion, substitution.

$$f_2(s, n) = (s+1) |\Sigma| f_2(s, n-1) + s f_2(s, n-1) + s (|\Sigma|-1) f_2(s, n-1)$$

I know it is not strict bound, because deleting a (previous inserted) insertion should not count. But am I far from true?

With the previous recursion (and knowing that $$f_2(s, 0) = 1$$), I would have:

$$f_2(s, n) = (|\Sigma| (2s + 1))^n$$

Is there a better bound?

• I have asked a very similar thing before. I don't think this is an easy problem. – Raphael Apr 25 at 13:57
• @Raphael Yes, I saw your question. But I thought that would somehow "correct" a word. In this case, the search space is (somewhat) more limited. – unamourdeswann Apr 25 at 14:04
• You're looking at a different metric, but other than that I think we're interested in the same thing. Mixing notation, $|\{w\}_k| = f_1(w, k)$. The final goal differs, though: you're looking for (bounds on) the maximal value for word length $n$ whereas I was looking for complexity of computing the exact number for a given set of words. – Raphael Apr 25 at 14:09
• Correcting words was the initial motivation for me; I was aiming at a rough idea of how much a dictionary would explode if annotated with all close-enough words. – Raphael Apr 25 at 14:11
• @Raphael Interesting question! – unamourdeswann Apr 25 at 14:17