A191588 T(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 and such that the parts have at most size 2.

1, 1, 1, 0, 2, 3, 0, 1, 3, 7, 0, 0, 3, 7, 13, 0, 0, 1, 6, 17, 27, 0, 0, 0, 4, 14, 36, 61, 0, 0, 0, 1, 10, 35, 77, 133, 0, 0, 0, 0, 5, 25, 81, 173, 287, 0, 0, 0, 0, 1, 15, 65, 183, 387, 633, 0, 0, 0, 0, 0, 6, 41, 161, 421, 857, 1407, 0, 0, 0, 0, 0, 1, 21, 112, 385, 969, 1911, 3121, 0, 0, 0, 0, 0, 0, 7, 63, 294, 918, 2211, 4287, 6943, 0, 0, 0, 0, 0, 0, 1, 28, 182, 742, 2181, 5040, 9619, 15517, 0, 0

Offset

1,5

Comments

Diagonal appears to be A098479. - Joerg Arndt, Jun 09 2011

T(m,n) is the number of lattice paths from (0,0) to (m,n) with steps in {(1,1),(1,2),(2,1)}. - Steffen Eger, Sep 25 2012

Links

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

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Formula

For m >= n: T(m,n) = C(n,2*n-m) + Sum_{k=2..n-1} C(k,2*k-n)*C(2*k-n,3*k-n-m) (note: C(2*k-n,3*k-n-m) = C(2*k-n,m-k)) where C(n,k) = binomial(n,k) for n >= k and 0 otherwise.

Symmetrically extended by T(n,m) = T(m,n).

Example

1
1 1
0 2 3
0 1 3 7
0 0 3 7 13
0 0 1 6 17 27
0 0 0 4 14 36 61
0 0 0 1 10 35 77 133
0 0 0 0  5 25 81 173 287
0 0 0 0  1 15 65 183 387 633
0 0 0 0  0  6 41 161 421 857 1407
0 0 0 0  0  1 21 112 385 969 1911 3121
0 0 0 0  0  0  7  63 294 918 2211 4287  6943
0 0 0 0  0  0  1  28 182 742 2181 5040  9619 15517
0 0 0 0  0  0  0   8  92 504 1842 5134 11508 21602 34755
Examples:
For m=3, n=2, we have
  x xx     xx x
  y  y      y y
For m=3, n=3, we have
  x xx     xx x   x x x
  yy y      y yy  y y y
For m=4, n=4, we have
  x xx x   x xx x   xx x x   xx x x   x x xx  x x xx   x x x x
  yy y y   y y yy   y yy y    y y yy  y yy y  yy y y   y y y y

Mathematica

t[m_, n_] /; m >= n := t[m, n] = Binomial[n, 2n - m] + Sum[Binomial[k, 2k - n]*Binomial[2k - n, 3k - n - m], {k, 2, n-1}]; t[m_, n_] /; m < n := t[m, n]; Table[t[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 07 2013, from formula *)

Crossrefs

Cf. A180091, A185287, A098479 (diagonal).

Sequence in context: A112168 A072516 A320782 * A106450 A255961 A297328

Adjacent sequences: A191585 A191586 A191587 * A191589 A191590 A191591

Keyword

nonn,nice,tabl

Author

Steffen Eger, Jun 09 2011

Status

approved