|
|
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 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).
|
|
LINKS
|
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|