1,5

A valley point is a path vertex that is preceded by a downstep and followed by an upstep (or by nothing at all). T(n,k) is the number of Dyck n-paths whose first valley point is at position k, 2<=k<=2n. - David Callan (callan(AT)stat.wisc.edu), Mar 02 2005

Row n has 2n-1 terms.

Row sums give the Catalan numbers (A000108).

Columns k=2 through 7 are respectively A000108, A000245, A071724, A002057, A071725, A026013. The nonzero entries in the even-indexed columns approach A088218 and similarly the odd-indexed columns approach A001791.

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

G.f. Sum_{2<=k<=2n}T(n, k)x^n*y^k = ((1 - (1 - 4*x)^(1/2))*y^2*(1 - x*y))/(2*(1 - ((1 - (1 - 4*x)^(1/2))*y)/2)*(1 - x*y^2)). With G:= (1 - (1 - 4*x)^(1/2))/2, the gf for column 2k is G(G^(2k+1)(G-x)-x^(k+1)(1-G))/(G^2-x) and for column 2k+1 is G(G-x)(G^(2k+2)-x^(k+1))/(G^2-x). - David Callan (callan(AT)stat.wisc.edu), Mar 02 2005

Triangle begins

\ k..2...3...4...5...6...7....

n

1 |..1

2 |..1...0...1

3 |..2...1...1...0...1

4 |..5...3...3...1...1...0...1

5 |.14...9...9...4...3...1...1...0...1

6 |.42..28..28..14..10...4...3...1...1...0...1

7 |132..90..90..48..34..15..10...4...3...1...1...0...1

T(4,3)=3 because we have UU(DU)DDUD, UU(DU)DUDD and UU(DU)UDDD, where U=(1,1), D=(1,-1) (the first valley, with abscissa 3, is shown between parentheses).

G:=t^2*z*C*(1-t*z)/(1-t^2*z)/(1-t*z*C): C:=(1-sqrt(1-4*z))/2/z: Gser:=simplify(series(G, z=0, 11)): for n from 1 to 10 do P[n]:=coeff(Gser, z^n) od: seq(seq(coeff(P[n], t^k), k=2..2*n), n=1..10);

Cf. A000108, A000245.

Sequence in context: A108934 A108947 A152459 this_sequence A143439 A105469 A136167

Adjacent sequences: A097605 A097606 A097607 this_sequence A097609 A097610 A097611

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 30 2004, Dec 22 2004

Edited by N. J. A. Sloane (njas(AT)research.att.com) at the suggestion of Andrew Plewe, Jun 23 2007