|
| |
|
|
A083381
|
|
Square array giving 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; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| Number of edges in the acylic 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.
|
|
|
FORMULA
| T(i, j) = 3*i*j + i + j. Recurrence: T(i, 0) = i, T(0, j) = j, T(i, j) = T(i-1, j) + T(i, j-1) - T(i-1, j-1) + 3
|
|
|
EXAMPLE
| Square array T(i,j) begins:
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
| Cf. A045944, A008288.
Sequence in context: A154751 A197545 A187017 * A197180 A129396 A153289
Adjacent sequences: A083378 A083379 A083380 * A083382 A083383 A083384
|
|
|
KEYWORD
| easy,nonn,tabl
|
|
|
AUTHOR
| Martin Jansche (jansche(AT)acm.org), Jun 05 2003
|
| |
|
|
