A097608 - OEIS

%I #10 Sep 24 2018 16:53:14

%S 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,

%T 3,1,1,0,1,132,90,90,48,34,15,10,4,3,1,1,0,1,429,297,297,165,117,55,

%U 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

%N 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).

%C 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

%C Row n has 2n-1 terms.

%C Row sums give the Catalan numbers (A000108).

%C 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.

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

%F 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

%e Triangle begins

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

%e n

%e 1 |..1

%e 2 |..1...0...1

%e 3 |..2...1...1...0...1

%e 4 |..5...3...3...1...1...0...1

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

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

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

%e 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).

%p 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);

%Y Cf. A000108, A000245.

%K nonn,tabf

%O 1,5

%A _Emeric Deutsch_, Aug 30 2004, Dec 22 2004

%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, Jun 23 2007