cp's OEIS Frontend

A180091 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.

%I A180091 #67 Nov 20 2024 09:52:57
%S A180091 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 A180091 1,7,23,55,118,237,450,817,1,8,30,79,180,380,755,1429,2599,1,9,38,110,
%U A180091 267,592,1229,2421,4570,8323
%N A180091 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 A180091 a(m,n) is also the number alignments (between two strings) that satisfy weak monotonicity, completeness, and disjointness.
%C A180091 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 A180091 From _Julien Rouyer_, Jun 02 2023: (Start)
%C A180091 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 A180091 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 A180091 A direct combinatorial calculation is possible, but time-consuming if m and n are large. (End)
%C A180091 From _Thierry Marchant_, Oct 30 2024: (Start)
%C A180091 a(m,n) is also the number of maximal antichains in the product of two chains of length m and n.
%C A180091 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 A180091 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 A180091 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 A180091 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 A180091 S. Eger, <a href="http://www.adiuvaris.eu/publications/descriptions.pdf">Derivation of sequence</a> [broken link]
%F A180091 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 A180091 Symmetrically extended to m <= n by a(m,n) = a(n,m).
%F A180091 a(n,n) = A171155(n-1).
%F A180091 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 A180091 For m=4, n=3, the 5 possibilities are:
%e A180091 a) X XXX   b) XXX X  c) X XX X  d) XX X X   e) X X XX
%e A180091    YY Y        Y YY     Y  Y Y     Y  Y Y      Y Y Y
%e A180091 The triangle a(m,n) starts in row m=1 with columns 1 <= n <= m as:
%e A180091   1;
%e A180091   1,  1;
%e A180091   1,  2,  3;
%e A180091   1,  3,  5,   9;
%e A180091   1,  4,  8,  15,  27;
%e A180091   1,  5, 12,  24,  46,   83;
%e A180091   1,  6, 17,  37,  75,  143,  259;
%e A180091   1,  7, 23,  55, 118,  237,  450,  817;
%e A180091   1,  8, 30,  79, 180,  380,  755, 1429,  2599;
%e A180091   1,  9, 38, 110, 267,  592, 1229, 2421,  4570,  8323;
%e A180091   1, 10, 47, 149, 386,  899, 1948, 3989,  7804, 14698, 26797;
%e A180091   1, 11, 57, 197, 545, 1334, 3015, 6412, 12987, 25264, 47491, 86659;
%e A180091 From _Julien Rouyer_, Jun 02 2023: (Start)
%e A180091 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 A180091     f(1)=1, f(2)=2;
%e A180091     g(1)=1, g(2)=3;
%e A180091     h(1)=2, h(2)=3;
%e A180091     i(1)=3;
%e A180091     j(2)=1. (End)
%p A180091 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 A180091 (Python)
%o A180091 # The following program gives T(m,n)=a(m+1,n+1) for any m >= 0 and n >= 0:
%o A180091 def T(m,n):
%o A180091     if n == 0:
%o A180091         res = 1
%o A180091     elif n == 1:
%o A180091         res = max(m,n)
%o A180091     elif m < n:
%o A180091         res = T(n,m)
%o A180091     else:
%o A180091         res = 0
%o A180091         for i in range(1,m+1):
%o A180091             res += T(m-i,n-1)
%o A180091         for j in range(2,n+1):
%o A180091             res += T(m-1,n-j)
%o A180091     return res # _Julien Rouyer_, Jun 02 2023
%Y A180091 Cf. A089071 (third column), A108626 (sums of diagonals).
%Y A180091 Main diagonal gives A171155.
%Y A180091 Cf. A047080.
%K A180091 easy,tabl,nonn
%O A180091 1,5
%A A180091 _Steffen Eger_, Jan 14 2011