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.

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

Offset: 1

Author

Steffen Eger, Jan 14 2011

Keywords

• easy
• tabl
• nonn

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)

Examples

			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)
		

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]

Crossrefs

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

Main diagonal gives A171155.

Cf. A047080.

Programs

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

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

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