OFFSET
0,7
COMMENTS
The Damerau-Levenshtein distance between two sequences is the number of edit operations (deletions, insertions, substitutions, and adjacent transpositions) needed to transform one into the other.
For consistency with A152487, the binary representation of 0 is assumed to be "0". If instead 0 is represented as the empty sequence, T(n,0) should be increased by 1 for all n except those of the form 2^m-1 for m >= 0.
T(n,k) <= A152487(n,k).
LINKS
Pontus von Brömssen, Rows n = 0..200, flattened
Wikipedia, Damerau-Levenshtein distance
EXAMPLE
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
0: 0
1: 1 0
2: 1 1 0
3: 2 1 1 0
4: 2 2 1 2 0
5: 2 2 1 1 1 0
6: 2 2 1 1 1 1 0
7: 3 2 2 1 2 1 1 0
8: 3 3 2 3 1 2 2 3 0
9: 3 3 2 2 1 1 2 2 1 0
10: 3 3 2 2 1 1 1 2 1 1 0
11: 3 3 2 2 2 1 2 1 2 1 1 0
12: 3 3 2 2 1 2 1 2 1 2 1 2 0
13: 3 3 2 2 2 1 1 1 2 1 2 1 1 0
...
The distance between the binary representations of 46 and 25 is 3 (via the edits "101110" - "10111" - "11011" - "11001"), so T(46,25) = 3.
CROSSREFS
KEYWORD
AUTHOR
Pontus von Brömssen, Dec 02 2018
STATUS
approved