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

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

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