The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 Table of n, a(n) for n=0..76. FORMULA T(i, j) = 3*i*j + i + j. Recurrence: T(i, 0) = i, T(0, j) = j, and T(i, j) = T(i-1, j) + T(i, j-1) - T(i-1, j-1) + 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 Cf. A008288, A045944 (main diagonal). Sequence in context: A299777 A197545 A187017 * A197180 A129396 A274602 Adjacent sequences: A083378 A083379 A083380 * A083382 A083383 A083384 KEYWORD easy,nonn,tabl AUTHOR Martin Jansche (jansche(AT)acm.org), Jun 05 2003 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 11 16:20 EDT 2024. Contains 375836 sequences. (Running on oeis4.)