A191588 - OEIS

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 #38 Dec 12 2015 13:11:16

%S 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 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 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 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 Diagonal appears to be A098479. - _Joerg Arndt_, Jun 09 2011

%C 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 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 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 Symmetrically extended by T(n,m) = T(m,n).

%e 1

%e 1 1

%e 0 2 3

%e 0 1 3 7

%e 0 0 3 7 13

%e 0 0 1 6 17 27

%e 0 0 0 4 14 36 61

%e 0 0 0 1 10 35 77 133

%e 0 0 0 0 5 25 81 173 287

%e 0 0 0 0 1 15 65 183 387 633

%e 0 0 0 0 0 6 41 161 421 857 1407

%e 0 0 0 0 0 1 21 112 385 969 1911 3121

%e 0 0 0 0 0 0 7 63 294 918 2211 4287 6943

%e 0 0 0 0 0 0 1 28 182 742 2181 5040 9619 15517

%e 0 0 0 0 0 0 0 8 92 504 1842 5134 11508 21602 34755

%e Examples:

%e For m=3, n=2, we have

%e x xx xx x

%e y y y y

%e For m=3, n=3, we have

%e x xx xx x x x x

%e yy y y yy y y y

%e For m=4, n=4, we have

%e x xx x x xx x xx x x xx x x x x xx x x xx x x x x

%e yy y y y y yy y yy y y y yy y yy y yy y y y y y y

%t 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 Cf. A180091, A185287, A098479 (diagonal).

%K nonn,nice,tabl

%O 1,5

%A _Steffen Eger_, Jun 09 2011