|
| |
|
|
A080936
|
|
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1<=k<=n).
|
|
2
| |
|
|
1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 15, 18, 7, 1, 1, 31, 57, 33, 9, 1, 1, 63, 169, 132, 52, 11, 1, 1, 127, 482, 484, 247, 75, 13, 1, 1, 255, 1341, 1684, 1053, 410, 102, 15, 1, 1, 511, 3669, 5661, 4199, 1975, 629, 133, 17, 1, 1, 1023, 9922, 18579, 16017, 8778, 3366, 912, 168
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| Sum of entries in row n is A000108(n) (the Catalan numbers).
|
|
|
REFERENCES
| N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.
G. Kreweras, Sur les eventails de segments, Cahiers du Bureau Universitaire de Recherche Operationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
|
|
|
FORMULA
| T(n, k) = A080934(n, k) - A080934(n, k-1).
The g.f. for Dyck paths of height k is h(k)=z^k/(f(k)*f(k+1)), where f(k) are Fibonacci type polynomials defined by f(0)=f(1)=1, f(k)=f(k-1)-z*f(k-2) or by f(k)=sum(i=0..floor(k/2), binom(k-i,i)*(-z)^i ). Incidentally, the g.f. for Dyck paths of height at most k is H(k)=f(k)/f(k+1). [Emeric Deutsch, Jun 8 2011]
|
|
|
EXAMPLE
| T(3,2)=3 because we have UUDDUD, UDUUDD, and UUDUDD, where U=(1,1) and D=(1,-1). The other two Dyck paths of semilength 3, UDUDUD and UUUDDD, have heights 1 and 3, respectively. [Emeric Deutsch, Jun 8 2011]
Triangle starts:
1;
1,1;
1,3,1;
1,7,5,1;
1,15,18,7,1;
1,31,57,33,9,1;
1,63,169,132,52,11,1;
|
|
|
MAPLE
| f := proc (k) options operator, arrow: sum(binomial(k-i, i)*(-z)^i, i = 0 .. floor((1/2)*k)) end proc: h := proc (k) options operator, arrow: z^k/(f(k)*f(k+1)) end proc: T := proc (n, k) options operator, arrow: coeff(series(h(k), z = 0, 25), z, n) end proc: for n to 11 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form [Emeric Deutsch, Jun 8 2011]
|
|
|
CROSSREFS
| Cf. A000108 (row sums), A079214, A080934, A080935.
Sequence in context: A177992 A112857 A118801 * A094507 A065625 A154341
Adjacent sequences: A080933 A080934 A080935 * A080937 A080938 A080939
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Henry Bottomley (se16(AT)btinternet.com), Feb 25 2003
|
| |
|
|
