The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 5
 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 (list; table; graph; refs; listen; history; text; internal format)
 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 LINKS M. A. Covington, The Number of Distinct Alignments of Two Strings, Journal of Quantitative Linguistics, Vol.11 (2004), Issue3, 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_{l=1..k-1} C(k,l)*C(n-k-1,k-l-1)*C(m+l-k-1,l-1). Symmetrically extended to m<=n by a(m,n)=a(n,m). a(n,n) = A171155(n-1). 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; 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 CROSSREFS Cf. A089071 (third column), A108626 (sums of diagonals). Main diagonal gives A171155. Sequence in context: A193923 A198811 A067337 * A047973 A020501 A283878 Adjacent sequences:  A180088 A180089 A180090 * A180092 A180093 A180094 KEYWORD easy,tabl,nonn AUTHOR Steffen Eger, Jan 14 2011 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 23 17:07 EDT 2021. Contains 346259 sequences. (Running on oeis4.)