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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080936 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1<=k<=n). 16
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, 19, 1 (list; table; graph; refs; listen; history; text; 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.

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

FindStat - Combinatorial Statistic Finder, The height of a Dyck path

FindStat - Combinatorial Statistic Finder, The height of a Dyck path., The depth of an ordered tree., The depth minus 1 of an ordered tree

A Joseph, P Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406, 2015

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]

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 08 2011

For all n >= 1 and floor((n+1)/2) <= k <= n we have: T(n,k) = 2*(2*k+3)*(2*k^2+6*k+1-3*n)*(2*n)!/((n-k)!*(n+k+3)!). - Gheorghe Coserea, Dec 06 2015

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 08 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 08 2011

# second Maple program:

b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,

      `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))

    end:

T:= (n, k)-> b(2*n, 0, k) -`if`(k=0, 0, b(2*n, 0, k-1)):

seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 06 2012

MATHEMATICA

b[x_, y_, k_] := b[x, y, k] = If[y > Min[k, x] || y<0, 0, If[x == 0, 1, b[x-1, y-1, k] + b[x-1, y+1, k]]]; T[n_, k_] := b[2*n, 0, k] - If[k == 0, 0, b[2*n, 0, k-1] ]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

CROSSREFS

Cf. A000108 (row sums), A079214, A080934, A080935, A259885, A259899, A289481.

Columns k=1-10 give: A000012, A000225(n-1), A258109, A262600, A289418, A289419, A289420, A289421, A289422, A289423.

T(2n,n) gives A268316.

Sequence in context: A177992 A112857 A118801 * A094507 A065625 A287213

Adjacent sequences:  A080933 A080934 A080935 * A080937 A080938 A080939

KEYWORD

nonn,tabl

AUTHOR

Henry Bottomley, Feb 25 2003

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 July 22 00:13 EDT 2017. Contains 289648 sequences.