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

%I #2 Mar 31 2012 10:22:44

%S 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,

%T 187,64,18,5,1,1,0,453,653,233,66,18,5,1,1,0,1367,2302,859,243,66,18,

%U 5,1,1,0,4191,8174,3189,906,245,66,18,5,1,1

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

%C 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.

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

%e Table begins

%e \ k..0....1....2....3....4....5....6....7

%e n

%e 0 |..1

%e 1 |..0....1

%e 2 |..0....1....1

%e 3 |..0....3....1....1

%e 4 |..0....7....5....1....1

%e 5 |..0...19...16....5....1....1

%e 6 |..0...53...54...18....5....1....1

%e 7 |..0..153..187...64...18....5....1....1

%e a(3,1)=3 because the Dyck 3-paths whose longest sawtooth has size 1 are

%e UUUDDD, UUDDUD, UDUUDD.

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

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

%K nonn,tabl

%O 0,8

%A _David Callan_, Jun 06 2006