A114489 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n that have k valleys at level 1.

1, 1, 2, 4, 1, 9, 4, 1, 22, 14, 5, 1, 58, 46, 21, 6, 1, 163, 149, 80, 29, 7, 1, 483, 484, 292, 124, 38, 8, 1, 1494, 1589, 1044, 498, 179, 48, 9, 1, 4783, 5288, 3701, 1928, 780, 246, 59, 10, 1, 15740, 17848, 13096, 7304, 3237, 1152, 326, 71, 11, 1, 52956, 61060, 46428

Offset: 0

Author

Emeric Deutsch, Dec 01 2005

Keywords

• nonn
• tabf

Comments

T(n,k) is also the number of Dyck paths of semilength n having k pairs of consecutive valleys at the same level. Example: T(4,1)=4 because we have U(DU)(DU)UDD, U(DU)UD(DU)D, UUD(DU)(DU)D, and UU(DU)(DU)DD, where U=(1,1), D=(1,-1); the pairs of consecutive same-level valleys are shown between parentheses. - Emeric Deutsch, Jun 19 2011

Rows 0 and 1 contain one term each; row n contains n-1 terms (n>=2).

Row sums are the Catalan numbers (A000108).

Column 0 yields A059019.

Sum(k*T(n,k), k=0..n-1) = 6*binomial(2*n-1,n-3)/(n+3) (A003517).

Examples

			T(4,1) = 4 because we have UU(DU)DDUD, UDUU(DU)DD, UU(DU)UDDD and UUUD(DU)DD, where U=(1,1), D=(1,-1); the valleys at level 1 are shown between parentheses.
Triangle starts:
1;
1;
2;
4,   1;
9,   4, 1;
22, 14, 5, 1;
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened

Crossrefs

Cf. A000108, A059019, A003517.

Programs

Maple

C:=(1-sqrt(1-4*z))/2/z: G:=(1-t*z*C)/(1-t*z*C-z+t*z^2*C-z^2*C): Gser:=simplify(series(G,z=0,17)): P[0]:=1: for n from 1 to 12 do P[n]:=coeff(Gser,z^n) od: 1; 1; for n from 2 to 12 do seq(coeff(t*P[n],t^j),j=1..n-1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, expand(b(x-1, y-1, 1)+
      `if`(t=1 and y=1, z, 1)*b(x-1, y+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, Mar 12 2014

Mathematica

b[x_, y_, t_] :=  b[x, y, t] = If[y>x || y<0, 0, If[x == 0, 1, Expand[b[x-1, y-1, 1] + If[t == 1 && y == 1, z, 1]*b[x-1, y+1, 0]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, May 20 2015, after Alois P. Heinz *)

Formula

G.f.: (1-t*z*C)/((1-z)*(1-t*z*C)-z^2*C), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.