A120060 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest sawtooth has size k.

1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 7, 5, 1, 1, 0, 19, 16, 5, 1, 1, 0, 53, 54, 18, 5, 1, 1, 0, 153, 187, 64, 18, 5, 1, 1, 0, 453, 653, 233, 66, 18, 5, 1, 1, 0, 1367, 2302, 859, 243, 66, 18, 5, 1, 1, 0, 4191, 8174, 3189, 906, 245, 66, 18, 5, 1, 1

Offset: 0

Author

David Callan, Jun 06 2006

Keywords

• nonn
• tabl

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.

Examples

			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.
		

Crossrefs

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

Programs

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

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