

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


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 npaths whose first valley point is at position k, 2<=k<=2n.  David Callan, Mar 02 2005
Row n has 2n1 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 evenindexed columns approach A088218 and similarly the oddindexed columns approach A001791.


LINKS

Table of n, a(n) for n=1..81.


FORMULA

G.f.=t^2*zC(1tz)/[(1t^2*z)(1tzC)], where C=[1sqrt(14z)]/(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)(Gx)x^(k+1)(1G))/(G^2x) and for column 2k+1 is G(Gx)(G^(2k+2)x^(k+1))/(G^2x).  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*(1t*z)/(1t^2*z)/(1t*z*C): C:=(1sqrt(14*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

Cf. A000108, A000245.
Sequence in context: A108947 A152459 A275784 * A168261 A180997 A143439
Adjacent sequences: A097605 A097606 A097607 * A097609 A097610 A097611


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



