0,8

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.

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

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.

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}]

Cf. A120059. Column k=1 is A078481. Row sums are the Catalan numbers A000108.

Sequence in context: A124801 A124926 A115378 this_sequence A143295 A104608 A110245

Adjacent sequences: A120057 A120058 A120059 this_sequence A120061 A120062 A120063

nonn,tabl

David Callan (callan(AT)stat.wisc.edu), Jun 06 2006