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

1, 1, 2, 4, 1, 10, 4, 29, 12, 1, 90, 36, 6, 290, 114, 24, 1, 960, 376, 86, 8, 3246, 1272, 303, 40, 1, 11164, 4380, 1074, 168, 10, 38934, 15293, 3838, 660, 60, 1, 137358, 54012, 13812, 2528, 290, 12, 489341, 192612, 50013, 9584, 1265, 84, 1

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn
• tabf

Comments

Each of rows 0, 1, 2 has one term; row n (n >= 1) has ceiling(n/2) terms. Row sums are the Catalan numbers (A000108). Column 0 yields A135334. - Emeric Deutsch, Dec 14 2007

Examples

			Triangle begins:
     1;
     1;
     2;
     4    1;
    10    4;
    29   12   1;
    90   36   6;
   290  114  24  1;
   960  376  86  8;
  3246 1272 303 40 1;
  ...
T(4,1)=4 because we have UDU(UDDU)D, U(UDDU)DUD, U(UDDU)UDD and UUD(UDDU)D (the UDDU's starting at level 1 are shown between parentheses).
		

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.

Crossrefs

Cf. A000108, A135334.

Programs

Maple

T:=proc(n,k) options operator, arrow: (2*k+2)*(sum((-1)^(j-k)*binomial(j+1, k+1)*binomial(2*n-2*j-1,n),j=k..floor((1/2)*n-1/2)))/(n+1) end proc: 1; for n to 13 do seq(T(n,k),k=0..ceil((n-2)*1/2)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 14 2007
G:=1+z*C^2/(1+(1-t)*z^2*C^2): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,16)): for n from 0 to 13 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; for n to 13 do seq(coeff(P[n],t,j),j=0..floor((n-1)*1/2)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 14 2007
# third Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y+1, `if`(y=1, 1, 0))*
      `if`(t=3, z, 1))+b(x-1, y-1, `if`(t in [1, 2], t+1, 0))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=0..14);  # Alois P. Heinz, Nov 16 2019

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0,
     If[x == 0, 1, Expand[b[x - 1, y + 1, If[y == 1, 1, 0]]*
     If[t == 3, z, 1]] + b[x - 1, y - 1, If[1 <= t <= 2, t + 1, 0]]]];
T[n_] := CoefficientList[b[2n, 0, 0], z];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

Formula

From Emeric Deutsch, Dec 14 2007: (Start)

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

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

Extensions

Edited and extended by Emeric Deutsch, Dec 14 2007