login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=0..65.

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 A289978 A185983

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 12:34 EDT 2018. Contains 316379 sequences. (Running on oeis4.)