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