The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #14 Oct 27 2019 05:18:01
%S 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,
%T 7,25,37,43,43,37,25,7,8,29,44,53,56,53,44,29,8,9,33,51,63,69,69,63,
%U 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
%N Square array giving the number of trellis edges T(i,j) (i >= 0, j >= 0), read by antidiagonals.
%C 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.
%C 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.
%F T(i, j) = 3*i*j + i + j.
%F 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.
%e Square array T(i,j) (with rows i >= 0 and columns j >= 0) begins as follows:
%e 0, 1, 2, 3, 4, ...
%e 1, 5, 9, 13, 17, ...
%e 2, 9, 16, 23, 30, ...
%e 3, 13, 23, 33, 43, ...
%e 4, 17, 30, 43, 56, ...
%e ...
%Y Cf. A008288, A045944 (main diagonal).
%K easy,nonn,tabl
%O 0,4
%A Martin Jansche (jansche(AT)acm.org), Jun 05 2003