OFFSET
1,5
COMMENTS
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, Mar 02 2005
Row n has 2n-1 terms.
Row sums give the Catalan numbers (A000108).
FORMULA
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, Mar 02 2005
EXAMPLE
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).
MAPLE
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);
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Aug 30 2004, Dec 22 2004
EXTENSIONS
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007
STATUS
approved