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)
From Thierry Marchant, Oct 30 2024: (Start)
a(m,n) is also the number of maximal antichains in the product of two chains of length m and n.
a(m,n) is also the number of strict chains in the product of two chains of length m and n (a strict chain P in a product of two chains is a chain such that x,y in P implies x_1 different from y_1 and x_2 different from y_2).
a(m,n) is also the number of walks from (0,0) to (m,n) where unit horizontal (+1,0), vertical (0,+1), and diagonal (+1,+1) steps are permitted but a horizontal step cannot be followed by a vertical step, nor vice versa. (End)
LINKS
D. Bouyssou, T. Marchant, and M. Pirlot, About maximal antichains in a product of two chains:A catch-all note, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.
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