A135330 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k UUDU's starting at level 0.

1, 1, 2, 4, 1, 10, 4, 28, 14, 85, 46, 1, 271, 151, 7, 893, 502, 35, 3013, 1697, 151, 1, 10351, 5828, 607, 10, 36075, 20293, 2353, 65, 127219, 71494, 8952, 346, 1, 453097, 254404, 33738, 1648, 13, 1627378, 913028, 126594, 7336, 104

Offset

0,3

Comments

Row n has 1+floor(n/3) terms. Row sums yield the Catalan numbers (A000108). Column 0 yields A135336. - Emeric Deutsch, Dec 14 2007

Links

Table of n, a(n) for n=0..44.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Formula

From Emeric Deutsch, Dec 14 2007: (Start)

T(n,k) = (1/(n+1))*Sum_{j=k..floor(n/3)} (-1)^(j-k)*(3j+1)*binomial(j,k)*binomial(2n-3j, n).

G.f.: C/(1 + (1-t)z^3*C^3), where C = (1-sqrt(1-4z))/(2z) is the g.f. of the Catalan numbers (A000108). (End)

Example

Triangle begins:
      1;
      1;
      2;
      4,    1;
     10,    4;
     28,   14;
     85,   46,   1;
    271,  151,   7;
    893,  502,  35;
   3013, 1697, 151,  1;
  10351, 5828, 607, 10;
  ...
T(4,1)=4 because we have UUDUDDUD, UUDUUDDD, UUDUDUDD and UDUUDUDD.

Maple

T:=proc(n, k) options operator, arrow: (sum((-1)^(j-k)*(3*j+1)*binomial(j, k)*binomial(2*n-3*j, n), j=k..floor((1/3)*n)))/(n+1) end proc: for n from 0 to 14 do seq(T(n, k), k=0..floor((1/3)*n)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 14 2007

Crossrefs

Cf. A000108, A135336.

Sequence in context: A228337 A114506 A114848 * A135328 A355144 A346419

Adjacent sequences: A135327 A135328 A135329 * A135331 A135332 A135333

Keyword

nonn,tabf

Author

N. J. A. Sloane, Dec 07 2007

Extensions

Edited and extended by Emeric Deutsch, Dec 14 2007

Status

approved