OFFSET
0,8
COMMENTS
A pyramid in a Dyck path is a subpath of the form U^k D^k with k>=1 (U=upstep, D=downstep). The longest pyramid is indicated by lowercase letters in the Dyck path UUDuuudddDUD and it has size 3.
FORMULA
Generating function for column k>=1 is F[k]-F[k-1] where F[k]:=(1 + x^(k+1) - ((1 + x^(k+1))^2 - 4*x)^(1/2))/(2*x).
EXAMPLE
Table begins
\ k..0....1....2....3....4....5....6....7
n
0 |..1
1 |..0....1
2 |..0....1....1
3 |..0....2....2....1
4 |..0....5....6....2....1
5 |..0...13...19....7....2....1
6 |..0...35...63...24....7....2....1
7 |..0...97..212...85...25....7....2....1
a(3,2)=2 because the Dyck 3-paths whose longest pyramid has size 2 are
UUDDUD, UDUUDD.
MATHEMATICA
Clear[a] (* a[n, k] is the number of Dyck n-paths whose longest pyramid has size <=k *) a[0, k_]/; k>=0 := 1 a[1, k_]/; k>=1 := 1 a[n_, k_]/; k>=n := 1/(n+1)Binomial[2n, n] a[n_, 0]/; n>=1 := 0 a[n_, k_]/; k<0:= 0 a[n_, k_]/; 1<=k && k<n && n>=2 := a[n, k] = Sum[a[j-1, k] a[n-j, k], {j, n}] - a[n-k-1, k] Table[a[n, k]-a[n, k-1], {n, 0, 8}, {k, 0, n}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
David Callan, Jun 06 2006
STATUS
approved