A185287 R(m,n) is the number of ways to split two strings x and y 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 of the y string have at most size 2.

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 3, 0, 0, 1, 4, 5, 3, 0, 0, 1, 5, 8, 7, 3, 0, 0, 1, 6, 12, 13, 7, 0, 0, 0, 1, 7, 17, 22, 16, 6, 0, 0, 0, 1, 8, 23, 35, 32, 17, 4, 0, 0, 0, 1, 9, 30, 53, 58, 39, 14, 0, 0, 0, 0, 1, 10, 38, 77, 98, 80, 40, 10, 0, 0

Offset

1,8

Links

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

Formula

R(m,n) = C(m-1,n-1) + Sum_{k=2..n-1} C(m+k-n-1,2*k-n-1)*C(k,2*k-n).

Example

1    0    0    0    0    0    0    0    0    0    0    0
1    1    2    0    0    0    0    0    0    0    0    0
1    2    3    3    3    0    0    0    0    0    0    0
1    3    5    7    7    6    4    0    0    0    0    0
1    4    8   13   16   17   14   10    5    0    0    0
1    5   12   22   32   39   40   35   25   15    6    0
1    6   17   35   58   80   95   97   86   65   41   21
1    7   23   53   98  151  201  233  238  213  167  112
1    8   30   77  157  267  392  505  577  587  532  427
1    9   38  108  241  448  718 1013 1273 1436 1458 1333
1   10   47  147  357  720 1250 1912 2612 3217 3590 3640
1   11   57  195  513 1116 2086 3434 5056 6728 8146 9011

Mathematica

r[m_, n_] := Binomial[m-1, n-1] + Sum[ Binomial[k, 2k-n]*Binomial[k+m-n-1, 2k-n-1], {k, 2, n-1}]; r[m_, n_] /; n > 2m-1 = 0; Flatten[ Table[ r[m-k+1, k], {m, 1, 12}, {k, 1, m}]] (* Jean-François Alcover, Nov 07 2011 *)

Prog

(PARI)
C(n, k)=if(n<k, 0, binomial(n, k));
R(m, n)=C(m-1, n-1)+sum(k=2, n-1, C(m+k-n-1, 2*k-n-1)*C(k, 2*k-n) );
for (d=1, 14, for(c=1, d, print1(R(d-c+1, c), ", ")))
/* Joerg Arndt, Mar 11 2011 */

Crossrefs

Cf. A180091.

Sequence in context: A296339 A362686 A104245 * A276554 A297323 A257654

Adjacent sequences: A185284 A185285 A185286 * A185288 A185289 A185290

Keyword

nonn,tabl,nice

Author

Steffen Eger, Feb 20 2011

Status

approved