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?