The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A120060 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest sawtooth has size k. 1
 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 (list; table; graph; refs; listen; history; text; internal format)
 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. LINKS 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 Cf. A120059. Column k=1 is A078481. Row sums are the Catalan numbers A000108. Sequence in context: A124926 A175946 A115378 * A143295 A330892 A289978 Adjacent sequences: A120057 A120058 A120059 * A120061 A120062 A120063 KEYWORD nonn,tabl AUTHOR David Callan, Jun 06 2006 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 7 12:58 EST 2023. Contains 360123 sequences. (Running on oeis4.)