OFFSET
1,5
COMMENTS
Diagonal appears to be A098479. - Joerg Arndt, Jun 09 2011
T(m,n) is the number of lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(2,1)}. - Steffen Eger, Sep 25 2012
LINKS
Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
FORMULA
For m >= n: T(m,n) = C(n,2*n-m) + Sum_{k=2..n-1} C(k,2*k-n)*C(2*k-n,3*k-n-m) (note: C(2*k-n,3*k-n-m) = C(2*k-n,m-k)) where C(n,k) = binomial(n,k) for n >= k and 0 otherwise.
Symmetrically extended by T(n,m) = T(m,n).
EXAMPLE
1
1 1
0 2 3
0 1 3 7
0 0 3 7 13
0 0 1 6 17 27
0 0 0 4 14 36 61
0 0 0 1 10 35 77 133
0 0 0 0 5 25 81 173 287
0 0 0 0 1 15 65 183 387 633
0 0 0 0 0 6 41 161 421 857 1407
0 0 0 0 0 1 21 112 385 969 1911 3121
0 0 0 0 0 0 7 63 294 918 2211 4287 6943
0 0 0 0 0 0 1 28 182 742 2181 5040 9619 15517
0 0 0 0 0 0 0 8 92 504 1842 5134 11508 21602 34755
Examples:
For m=3, n=2, we have
x xx xx x
y y y y
For m=3, n=3, we have
x xx xx x x x x
yy y y yy y y y
For m=4, n=4, we have
x xx x x xx x xx x x xx x x x x xx x x xx x x x x
yy y y y y yy y yy y y y yy y yy y yy y y y y y y
MATHEMATICA
t[m_, n_] /; m >= n := t[m, n] = Binomial[n, 2n - m] + Sum[Binomial[k, 2k - n]*Binomial[2k - n, 3k - n - m], {k, 2, n-1}]; t[m_, n_] /; m < n := t[m, n]; Table[t[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 07 2013, from formula *)
CROSSREFS
KEYWORD
AUTHOR
Steffen Eger, Jun 09 2011
STATUS
approved