Number of ordered pairs of n-length binary strings with edit distance n-1

Question

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$.

Answer 1

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.