A114486 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k UUDD's starting at level 0; here U=(1,1), D=(1,-1) (0<=k<=floor(n/2)).

1, 1, 1, 1, 3, 2, 10, 3, 1, 31, 8, 3, 98, 27, 6, 1, 321, 88, 16, 4, 1078, 287, 54, 10, 1, 3686, 960, 183, 28, 5, 12789, 3280, 616, 95, 15, 1, 44919, 11378, 2106, 332, 45, 6, 159407, 39953, 7323, 1152, 155, 21, 1, 570704, 141752, 25785, 4028, 556, 68, 7

Offset

0,5

Comments

Row n has 1+floor(n/2) terms.

Links

Seiichi Manyama, Rows n = 0..200, flattened

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

Formula

G.f. G=G(t, z) satisfies G=1+z(C-z+tz)G, where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. G=2/[1+2z^2-2tz^2+sqrt(1-4z)].

Sum_{k=0..floor(n/2)} k*T(n,k) = A000108(n-1) (the Catalan numbers).

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

Example

T(5,2)=3 because we have UUDDUUDDUD, UUDDUDUUDD and UDUUDDUUDD, where U=(1,1), D=(1,-1).
Triangle starts:
   1;
   1;
   1,  1;
   3,  2;
  10,  3, 1;
  31,  8, 3;
  98, 27, 6, 1;
  ...

Maple

C:=(1-sqrt(1-4*z))/2/z: eq:=G=1+z*(C-z+t*z)*G: G:=solve(eq, G): Gser:=simplify(series(G, z=0, 17)): P[0]:=1: for n from 1 to 15 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 15 do seq(coeff(t*P[n], t^j), j=1..1+floor(n/2)) od; # yields sequence in triangular form

Prog

(PARI) T(n, k) = sum(j=k, n\2, (-1)^(j-k)*(j+1)*binomial(j, k)*binomial(2*n-3*j+1, n-2*j)/(2*n-3*j+1)); \\ Seiichi Manyama, Nov 06 2025

Crossrefs

Row sums are the Catalan numbers (A000108).

Column 0 yields A114487.

Sequence in context: A292923 A354191 A135515 * A176743 A220466 A090780

Adjacent sequences: A114483 A114484 A114485 * A114487 A114488 A114489

Keyword

nonn,tabf

Author

Emeric Deutsch, Nov 30 2005

Status

approved