

A083381


Square array giving the number of trellis edges T(i,j) (i >= 0, j >= 0), read by antidiagonals.


0



0, 1, 1, 2, 5, 2, 3, 9, 9, 3, 4, 13, 16, 13, 4, 5, 17, 23, 23, 17, 5, 6, 21, 30, 33, 30, 21, 6, 7, 25, 37, 43, 43, 37, 25, 7, 8, 29, 44, 53, 56, 53, 44, 29, 8, 9, 33, 51, 63, 69, 69, 63, 51, 33, 9, 10, 37, 58, 73, 82, 85, 82, 73, 58, 37, 10, 11, 41, 65, 83, 95, 101, 101, 95, 83, 65, 41
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Number of edges in the acyclic graph ("trellis") whose vertices are pairs (m,n) of natural numbers with 0 <= m <= i and 0 <= n <= j and which has edges from (m,n) to (m+1,n), (m,n+1) and (m+1,n+1). The number of edges of this graph is T(i,j), the array represented by the present sequence.
The number of paths from (0,0) to (i,j) is given by the Delannoy number D(i,j) (A008288). The main diagonal T(n,n) is the sequence A045944. Arises in dynamic programming algorithms for computing the string edit distance (Levenshtein distance) for strings of lengths i and j.


LINKS



FORMULA

T(i, j) = 3*i*j + i + j.
Recurrence: T(i, 0) = i, T(0, j) = j, and T(i, j) = T(i1, j) + T(i, j1)  T(i1, j1) + 3 for i, j >= 1.


EXAMPLE

Square array T(i,j) (with rows i >= 0 and columns j >= 0) begins as follows:
0, 1, 2, 3, 4, ...
1, 5, 9, 13, 17, ...
2, 9, 16, 23, 30, ...
3, 13, 23, 33, 43, ...
4, 17, 30, 43, 56, ...
...


CROSSREFS



KEYWORD



AUTHOR

Martin Jansche (jansche(AT)acm.org), Jun 05 2003


STATUS

approved



