A180091 - OEIS

%I #67 Nov 20 2024 09:52:57

%S 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,

%T 1,7,23,55,118,237,450,817,1,8,30,79,180,380,755,1429,2599,1,9,38,110,

%U 267,592,1229,2421,4570,8323

%N a(m,n) is the number of ways to split two strings of length m and n, respectively, into the same number of nonempty parts such that at least one of the corresponding parts has length 1.

%C a(m,n) is also the number alignments (between two strings) that satisfy weak monotonicity, completeness, and disjointness.

%C 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

%C From _Julien Rouyer_, Jun 02 2023: (Start)

%C 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).

%C 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.

%C A direct combinatorial calculation is possible, but time-consuming if m and n are large. (End)

%C From _Thierry Marchant_, Oct 30 2024: (Start)

%C a(m,n) is also the number of maximal antichains in the product of two chains of length m and n.

%C 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).

%C 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)

%H D. Bouyssou, T. Marchant, and M. Pirlot, <a href="https://doi.org/10.48550/arXiv.2410.16243">About maximal antichains in a product of two chains:A catch-all note</a>, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.

%H M. A. Covington, <a href="https://doi.org/10.1080/0929617042000314921">The Number of Distinct Alignments of Two Strings</a>, Journal of Quantitative Linguistics, Vol. 11 (2004), Issue 3, pp. 173-182.

%H S. Eger, <a href="http://www.adiuvaris.eu/publications/descriptions.pdf">Derivation of sequence</a> [broken link]

%F 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).

%F Symmetrically extended to m <= n by a(m,n) = a(n,m).

%F a(n,n) = A171155(n-1).

%F 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

%e For m=4, n=3, the 5 possibilities are:

%e a) X XXX   b) XXX X  c) X XX X  d) XX X X   e) X X XX

%e    YY Y        Y YY     Y  Y Y     Y  Y Y      Y Y Y

%e The triangle a(m,n) starts in row m=1 with columns 1 <= n <= m as:

%e   1;

%e   1,  1;

%e   1,  2,  3;

%e   1,  3,  5,   9;

%e   1,  4,  8,  15,  27;

%e   1,  5, 12,  24,  46,   83;

%e   1,  6, 17,  37,  75,  143,  259;

%e   1,  7, 23,  55, 118,  237,  450,  817;

%e   1,  8, 30,  79, 180,  380,  755, 1429,  2599;

%e   1,  9, 38, 110, 267,  592, 1229, 2421,  4570,  8323;

%e   1, 10, 47, 149, 386,  899, 1948, 3989,  7804, 14698, 26797;

%e   1, 11, 57, 197, 545, 1334, 3015, 6412, 12987, 25264, 47491, 86659;

%e From _Julien Rouyer_, Jun 02 2023: (Start)

%e 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

%e     f(1)=1, f(2)=2;

%e     g(1)=1, g(2)=3;

%e     h(1)=2, h(2)=3;

%e     i(1)=3;

%e     j(2)=1. (End)

%p 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

%o (Python)

%o # The following program gives T(m,n)=a(m+1,n+1) for any m >= 0 and n >= 0:

%o def T(m,n):

%o     if n == 0:

%o         res = 1

%o     elif n == 1:

%o         res = max(m,n)

%o     elif m < n:

%o         res = T(n,m)

%o     else:

%o         res = 0

%o         for i in range(1,m+1):

%o             res += T(m-i,n-1)

%o         for j in range(2,n+1):

%o             res += T(m-1,n-j)

%o     return res # _Julien Rouyer_, Jun 02 2023

%Y Cf. A089071 (third column), A108626 (sums of diagonals).

%Y Main diagonal gives A171155.

%Y Cf. A047080.

%K easy,tabl,nonn,changed

%O 1,5

%A _Steffen Eger_, Jan 14 2011