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
Examples
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
Links
- Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
Programs
-
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 *)
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).
Comments