cp's OEIS Frontend

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.

%I A191588 #38 Dec 12 2015 13:11:16
%S A191588 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,
%T A191588 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,
%U A191588 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
%N 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.
%C A191588 Diagonal appears to be A098479. - _Joerg Arndt_, Jun 09 2011
%C A191588 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
%H A191588 Steffen Eger, <a href="http://arxiv.org/abs/1511.00622">On the Number of Many-to-Many Alignments of N Sequences</a>, arXiv:1511.00622 [math.CO], 2015.
%F A191588 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.
%F A191588 Symmetrically extended by T(n,m) = T(m,n).
%e A191588 1
%e A191588 1 1
%e A191588 0 2 3
%e A191588 0 1 3 7
%e A191588 0 0 3 7 13
%e A191588 0 0 1 6 17 27
%e A191588 0 0 0 4 14 36 61
%e A191588 0 0 0 1 10 35 77 133
%e A191588 0 0 0 0  5 25 81 173 287
%e A191588 0 0 0 0  1 15 65 183 387 633
%e A191588 0 0 0 0  0  6 41 161 421 857 1407
%e A191588 0 0 0 0  0  1 21 112 385 969 1911 3121
%e A191588 0 0 0 0  0  0  7  63 294 918 2211 4287  6943
%e A191588 0 0 0 0  0  0  1  28 182 742 2181 5040  9619 15517
%e A191588 0 0 0 0  0  0  0   8  92 504 1842 5134 11508 21602 34755
%e A191588 Examples:
%e A191588 For m=3, n=2, we have
%e A191588   x xx     xx x
%e A191588   y  y      y y
%e A191588 For m=3, n=3, we have
%e A191588   x xx     xx x   x x x
%e A191588   yy y      y yy  y y y
%e A191588 For m=4, n=4, we have
%e A191588   x xx x   x xx x   xx x x   xx x x   x x xx  x x xx   x x x x
%e A191588   yy y y   y y yy   y yy y    y y yy  y yy y  yy y y   y y y y
%t A191588 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 *)
%Y A191588 Cf. A180091, A185287, A098479 (diagonal).
%K A191588 nonn,nice,tabl
%O A191588 1,5
%A A191588 _Steffen Eger_, Jun 09 2011