|
Search: id:A083381
|
|
|
| A083381 |
|
Square array giving number of trellis edges T(i,j) (i >= 0, j >= 0), read by antidiagonals. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
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: A087892 A078372 A154751 this_sequence A129396 A153289 A161643
Adjacent sequences: A083378 A083379 A083380 this_sequence A083382 A083383 A083384
|
|
KEYWORD
|
easy,nonn,tabl
|
|
AUTHOR
|
Martin Jansche (jansche(AT)acm.org), Jun 05 2003
|
|
|
Search completed in 0.002 seconds
|
