OFFSET
0,8
COMMENTS
A sawtooth in a Dyck path is a subpath of the form (UD)^k with k>=1 (U=upstep, D=downstep). The longest sawtooth in the Dyck path UududUududDUDD has size 2; there are two of them, indicated by lowercase letters.
FORMULA
Generating function for column k>=1 is F[k]-F[k-1] where F[k]:=(Sum[x^j,{j,0,k+1}]-Sqrt[Sum[x^j,{j,0,k+1}]^2] - 4x Sum[x^j,{j,0,k}]^2)/ (2x Sum[x^j,{j,0,k}]).
EXAMPLE
Table begins
\ k..0....1....2....3....4....5....6....7
n
0 |..1
1 |..0....1
2 |..0....1....1
3 |..0....3....1....1
4 |..0....7....5....1....1
5 |..0...19...16....5....1....1
6 |..0...53...54...18....5....1....1
7 |..0..153..187...64...18....5....1....1
a(3,1)=3 because the Dyck 3-paths whose longest sawtooth has size 1 are
UUUDDD, UUDDUD, UDUUDD.
MATHEMATICA
Clear[a, b, c] (* a[n, k] is the number of Dyck n-paths whose longest sawtooth has size <=k, b[n, k] is the number of Dyck n-paths that start UU whose longest sawtooth has size <=k, c[n, k] is the number of Dyck n-paths that start UD whose longest sawtooth has size <=k *) catalanNumber[n_] := 1/(n+1)Binomial[2n, n] a[0, k_]/; k>=0 := 1; a[1, k_]/; k>=1 := 1; a[n_, 0]/; n>=1 := 0; a[n_, k_]/; k<0 := 0; b[1, k_]/; k>=0 := 0; c[1, k_]/; k>=1 := 1; b[n_, k_] := a[n, k] - c[n, k] c[n_, k_]/; 1<=k<=n-1 := c[n, k] = Sum[b[n-j, k], {j, k}] c[n_, k_]/; k>=n>=1 := catalanNumber[n-1]; a[n_, k_]/; k>=n>=0 := catalanNumber[n]; a[n_, k_]/; k==n-1 := catalanNumber[n]-1; a[n_, k_]/; 1<=k<=n-2 && n>=3 := a[n, k] = Sum[b[n-j, k], {j, k}] + Sum[a[j-1, k]a[n-j, k], {j, 2, n}] 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