1
$\begingroup$

An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed to transform one string into the other one.

How many ordered pairs of binary strings of length $n$ are there with edit distance exactly $n-1$?

For $n = 1,\dots, 10$ the exact numbers are $2, 8, 26, 54, 92, 138, 192, 254, 324, 402, 488, 582$ which is not in the OEIS. For $n=3$ the full list of pairs is:

000 011
000 101
000 110
001 010
001 100
001 111
010 001
010 100
010 101
010 111
011 000
011 101
011 110
100 001
100 010
100 111
101 000
101 010
101 011
101 110
110 000
110 011
110 101
111 001
111 010
111 100

For comparison, the number of ordered pairs of binary strings of length $n$ which have edit distance exactly $n$ is $2n$.

$\endgroup$
1
$\begingroup$

Feeding these numbers to Wolfram|Alpha yields these iterated differences:

\begin{array} 2 & & 8 & & 26 & & 54 & & 92 & & 138 & & 192 & & 254 & & 324 & & 402\\ & 6 & & 18 & & 28 & & 38 & & 46 & & 54 & & 62 & & 70 & & 78 & \\ & & 12 & & 10 & & 10 & & 8 & & 8 & & 8 & & 8 & & 8 & & \\ & & & -2 & & 0 & & -2 & & 0 & & 0 & & 0 & & 0 & & & \\ & & & & 2 & & -2 & & 2 & & 0 & & 0 & & 0 & & & & \\ & & & & & -4 & & 4 & & -2 & & 0 & & 0 & & & & & \\ & & & & & & 8 & & -6 & & 2 & & 0 & & & & & & \\ & & & & & & & -14 & & 8 & & -2 & & & & & & & \\ & & & & & & & & 22 & & -10 & & & & & & & & \\ & & & & & & & & & -32 & & & & & & & & & \end{array}

That seems to indicate that except for the first three terms the sequence is given by a quadratic polynomial. Trying again without the first three terms yields the polynomial $2\left(2n^2+13n+12\right)$. Since you seem to have code for producing initial terms, maybe you can produce a few more to check this. In view of the result for Average number of strings with edit distance exactly 2, it seems plausible that the result would be a polynomial. If you need a proof, some of the ideas I applied in the answer to that question may prove helpful.

$\endgroup$
6
  • $\begingroup$ I added two more numbers to the list. Amazingly Wolfram Alpha does seem to have found a closed form answer! A proof would be awesome and I will look at your other answer to see if I can get anything from it. $\endgroup$ – fomin Mar 4 '20 at 9:34
  • $\begingroup$ @fomin: Well, the cubic polynomial checks out for those two values, so that should be good enough as far as empirical evidence goes. $\endgroup$ – joriki Mar 4 '20 at 9:37
  • $\begingroup$ Do you mean quadratic polynomial? $\endgroup$ – fomin Mar 4 '20 at 9:51
  • $\begingroup$ @fomin: Yes; somehow I thought that the third row of differences being zero implies degree $3$, but you're right, it's quadratic, obviously. $\endgroup$ – joriki Mar 4 '20 at 9:56
  • $\begingroup$ Do you have any intuition for why the first three terms should be exceptional? $\endgroup$ – fomin Mar 4 '20 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.