OFFSET
1,5
COMMENTS
a(m,n) is also the number alignments (between two strings) that satisfy weak monotonicity, completeness, and disjointness.
a(m,n) is also the number of monotone lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(1,3),(1,4),...,(2,1),(3,1),(4,1),...}. - Steffen Eger, Sep 25 2012
From Julien Rouyer, Jun 02 2023: (Start)
a(m-1,n-1) is also the number of strictly increasing functions defined on a part of the m-set {1,...,m} that take values in the n-set {1,...,n} and that can't be extended to a greater part of the m-set to give another strictly increasing function (values for m < n can be obtained by symmetry).
a(m-1,n-1) is also the number of solutions to the problem consisting of connecting, with noncrossing edges, some of m points aligned on a straight line to some of n other points aligned on a parallel straight line (each point is connected at most with one other point), in such a way that no additional noncrossing connection can be added.
A direct combinatorial calculation is possible, but time-consuming if m and n are large. (End)
LINKS
M. A. Covington, The Number of Distinct Alignments of Two Strings, Journal of Quantitative Linguistics, Vol. 11 (2004), Issue 3, pp. 173-182.
S. Eger, Derivation of sequence [broken link]
FORMULA
For m >= n: a(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} Sum_{i=1..k-1} C(k,i)*C(n-k-1,k-i-1)*C(m+i-k-1,i-1).
Symmetrically extended to m <= n by a(m,n) = a(n,m).
a(n,n) = A171155(n-1).
a(m,n) = Sum_{i=1..m} a(m-i,n-1) + Sum_{j=2..n} a(m-1,n-j). - Julien Rouyer, Jun 02 2023
EXAMPLE
For m=4, n=3, the 5 possibilities are:
a) X XXX b) XXX X c) X XX X d) XX X X e) X X XX
YY Y Y YY Y Y Y Y Y Y Y Y Y
The triangle a(m,n) starts in row m=1 with columns 1 <= n <= m as:
1;
1, 1;
1, 2, 3;
1, 3, 5, 9;
1, 4, 8, 15, 27;
1, 5, 12, 24, 46, 83;
1, 6, 17, 37, 75, 143, 259;
1, 7, 23, 55, 118, 237, 450, 817;
1, 8, 30, 79, 180, 380, 755, 1429, 2599;
1, 9, 38, 110, 267, 592, 1229, 2421, 4570, 8323;
1, 10, 47, 149, 386, 899, 1948, 3989, 7804, 14698, 26797;
1, 11, 57, 197, 545, 1334, 3015, 6412, 12987, 25264, 47491, 86659;
From Julien Rouyer, Jun 02 2023: (Start)
There are a(5)=T(3,2)=5 strictly increasing functions defined on a part of {1,2,3} that take values in {1,2} and can't be extended keeping the same properties. The 5 functions are defined by
f(1)=1, f(2)=2;
g(1)=1, g(2)=3;
h(1)=2, h(2)=3;
i(1)=3;
j(2)=1. (End)
MAPLE
A180091 := proc(m, n) a := binomial(m-1, n-1); for k from 2 to n-1 do for l from 1 to k-1 do if k-l-1 >= 0 and k-l-1 <= n-k-1 and l-1 >=0 and l-1 <= m+l-k-1 then a := a+ binomial(k, l)*binomial(n-k-1, k-l-1)*binomial(m+l-k-1, l-1); end if; end do: end do: a; end proc: # R. J. Mathar, Feb 01 2011
PROG
(Python)
# The following program gives T(m, n)=a(m+1, n+1) for any m >= 0 and n >= 0:
def T(m, n):
if n == 0:
res = 1
elif n == 1:
res = max(m, n)
elif m < n:
res = T(n, m)
else:
res = 0
for i in range(1, m+1):
res += T(m-i, n-1)
for j in range(2, n+1):
res += T(m-1, n-j)
return res # Julien Rouyer, Jun 02 2023
CROSSREFS
KEYWORD
AUTHOR
Steffen Eger, Jan 14 2011
STATUS
approved