A143952 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peak plateaux (0<=k<=floor(n/2)). A peak plateau is a run of consecutive peaks that is preceded by an upstep and followed by a down step; a peak consists of an upstep followed by a downstep.

1, 1, 1, 1, 1, 4, 1, 12, 1, 1, 33, 8, 1, 88, 42, 1, 1, 232, 183, 13, 1, 609, 717, 102, 1, 1, 1596, 2622, 624, 19, 1, 4180, 9134, 3275, 205, 1, 1, 10945, 30691, 15473, 1650, 26, 1, 28656, 100284, 67684, 11020, 366, 1, 1, 75024, 320466, 279106, 64553, 3716, 34, 1

Offset: 0

Author

Emeric Deutsch, Oct 10 2008

Keywords

• nonn
• tabf

Comments

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

Row sums are the Catalan numbers (A000108).

T(n,1)=A027941(n-1)=Fibonacci(2n-1)-1.

Sum(k*T(n,k),k=0..floor(n/2))=A079309(n-1).

For the statistic "number of peaks in peak plateaux", see A143953.

Examples

			T(3,1)=4 because we have UD(UUDD), (UUDD)UD, (UUDUDD) and U(UUDD)D (the peak plateaux are shown between parentheses).
The triangle starts:
1;
1;
1,1;
1,4;
1,12,1;
1,33,8;
1,88,42,1;
		

Links

• David Callan, Kreweras's Narayana Number Identity Has a Simple Dyck Path Interpretation .

Crossrefs

Cf. A000045, A000108, A027941, A079309, A143953.

Programs

Maple

C:=proc(z) options operator, arrow: (1/2-(1/2)*sqrt(1-4*z))/z end proc: G:=(1-z)*C(z*(1-z)^2/(1-z+z^2-t*z^2)^2)/(1-z+z^2-t*z^2): Gser:=simplify(series(G,z= 0,17)): for n from 0 to 14 do P[n]:=sort(coeff(Gser,z,n)) end do: for n from 0 to 14 do seq(coeff(P[n],t,j),j=0..floor((1/2)*n)) end do; # yields sequence in triangular form

Formula

The g.f. G=G(t,z) satisfies z(1-z)G^2 - (1-z+z^2-tz^2)G+1-z = 0 (for the explicit form of G see the Maple program).

The trivariate g.f. g=g(x,y,z) of Dyck paths with respect to number of peak plateaux, number of peaks in the peak plateaux and semilength, marked, by x, y and z, respectively satisfies g=1+zg[g+xyz/(1-yz)-z/(1-z)].

T(n,k) = Sum_{r=1..n} Narayana(n-r,k)*binomial(2n-r-k,r-k) where Narayana(n,k) := binomial(n,k)*binomial(n,k-1)/n is the Narayana number A001263. - David Callan, Oct 31 2008