A097608 Triangle read by rows: number of Dyck paths of semilength n and having abscissa of the leftmost valley equal to k (if no valley, then it is taken to be 2n; 2<=k<=2n).
1, 1, 0, 1, 2, 1, 1, 0, 1, 5, 3, 3, 1, 1, 0, 1, 14, 9, 9, 4, 3, 1, 1, 0, 1, 42, 28, 28, 14, 10, 4, 3, 1, 1, 0, 1, 132, 90, 90, 48, 34, 15, 10, 4, 3, 1, 1, 0, 1, 429, 297, 297, 165, 117, 55, 35, 15, 10, 4, 3, 1, 1, 0, 1, 1430, 1001, 1001, 572, 407, 200, 125, 56, 35, 15, 10, 4, 3, 1, 1, 0, 1
Offset: 1
Examples
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).
Programs
-
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);
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
Extensions
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007
Comments