|
| |
|
|
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 A330892 A289978
Adjacent sequences: A120057 A120058 A120059 * A120061 A120062 A120063
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
David Callan, Jun 06 2006
|
|
|
STATUS
|
approved
|
| |
|
|
