login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A114848 Triangle read by rows T(n,k) = the number of Dyck paths of semilength n with k UUDDU's, 0<=k<=[(n-1)/2]. 3
1, 1, 2, 4, 1, 10, 4, 28, 13, 1, 82, 44, 6, 248, 153, 27, 1, 770, 536, 116, 8, 2440, 1889, 486, 46, 1, 7858, 6696, 1992, 240, 10, 25644, 23849, 8042, 1180, 70, 1, 84618, 85276, 32124, 5552, 430, 12, 281844, 305933, 127287, 25306, 2430, 99, 1, 946338, 1100692 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Row sums are Catalan numbers A000108.

LINKS

Alois P. Heinz, Rows n = 0..200, flattened

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. - From N. J. A. Sloane, May 05 2012

FORMULA

T(n,k) = Sum((-1)^j * binomial(n-1-(j+k), j+k) * binomial(j + k, k) * A000108(n-2(j+k)), j=0..[(n-1)/2]-k).

G.f. G = G(t,z) satisfies G = C(z/(z^2(1-t)+1)), where C(z) is g.f. of Catalan numbers.

EXAMPLE

T(4,1) = 4 because there exist 4 Dyck paths with one occurrence of UUDDU : UDUUDDUD, UUDDUDUD, UUDDUUDD, UUUDDUDD.

Triangle begins:

:  0 :     1;

:  1 :     1;

:  2 :     2;

:  3 :     4,     1;

:  4 :    10,     4;

:  5 :    28,    13,     1;

:  6 :    82,    44,     6;

:  7 :   248,   153,    27,    1;

:  8 :   770,   536,   116,    8;

:  9 :  2440,  1889,   486,   46,   1;

: 10 :  7858,  6696,  1992,  240,  10;

: 11 : 25644, 23849,  8042, 1180,  70,  1;

: 12 : 84618, 85276, 32124, 5552, 430, 12;

MAPLE

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,

     `if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 3, 2, 2][t])

      *`if`(t=5, z, 1) +b(x-1, y-1, [1, 1, 4, 5, 1][t]))))

    end:

T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):

seq(T(n), n=0..15);  # Alois P. Heinz, Jun 10 2014

MATHEMATICA

For[n = 1, n <= 20, n++, For[k = 0, k <= Floor[(n - 1)/2], k++, Print[Sum[(-1)^j * Binomial[n - 1 - (j + k), j + k] * Binomial[j + k, k] * Binomial[2(n - 2(j + k)), n - 2(j + k)]/(n - 2(j + k) + 1), {j, 0, Floor[(n - 1)/2] - k}]]]]

CROSSREFS

Cf. A187256, A243752.

Sequence in context: A211244 A228337 A114506 * A135330 A135328 A048941

Adjacent sequences:  A114845 A114846 A114847 * A114849 A114850 A114851

KEYWORD

nonn,tabf

AUTHOR

I. Tasoulas (jtas(AT)unipi.gr), Feb 20 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 05:00 EDT 2020. Contains 337346 sequences. (Running on oeis4.)