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