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

 

Logo


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

Table of n, a(n) for n=1..55.

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.

License Agreements, Terms of Use, Privacy Policy. .

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