login
The OEIS is supported by the many generous donors 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). 38
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).
From Gus Wiseman, Nov 16 2022: (Start)
Also the number of unlabeled ordered rooted trees with n nodes and height k. For example, row n = 5 counts the following trees:
(oooo) ((o)oo) (((o))o) ((((o))))
((oo)o) (((o)o))
((ooo)) (((oo)))
(o(o)o) ((o(o)))
(o(oo)) (o((o)))
(oo(o))
((o)(o))
(End)
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
Tomás Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Martínez Mori, Casandra D. Monroe, Daniel Quiñonez, Dirk Tolson III, and Dwight Anderson Williams II, Interval and L-interval Rational Parking Functions, arXiv:2311.14055 [math.CO], 2023. See p. 11.
FindStat - Combinatorial Statistic Finder, The height of a Dyck path
A. Joseph and P. Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406 [math.CO], 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]
Kevin Limanta, Hopein Christofen Tang, and Yozef Tjandra, Permutation-generated maps between Dyck paths, arXiv:2105.14439 [math.CO], 2021. Mentions this sequence.
Thomas Tunstall, Tim Rogers, and Wolfram Möbius, Assisted percolation of slow-spreading mutants in heterogeneous environments, arXiv:2303.01579 [q-bio.PE], 2023.
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)} binomial(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
T(n, k) = Sum_{i=1..k-1} (-1)^(i+1) * (Sum_{j=1..n} (Sum_{x=0..n} (-1)^(j+x) * binomial(x+2n-2j+1,x))) * a(k-i); a(1)=1, a(0)=0. - Tim C. Flowers, May 14 2018
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 *)
aot[n_]:=If[n==1, {{}}, Join@@Table[Tuples[aot/@c], {c, Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n], Depth[#]-2==k&]], {n, 1, 9}, {k, 1, n-1}] (* Gus Wiseman, Nov 16 2022 *)
PROG
(C++ 11)
#include <iostream>
#include <cmath>
using namespace std;
long long b, d, c, coefficient[1000], n, m, num[1000], p=0, k;
int binomialCoeff(long long b, long long d)
{
if (d==0 || d==b)
return 1;
return binomialCoeff(b-1, d-1) + binomialCoeff(b-1, d);
}
int main()
{
num[1]=1;
cin>>m; //total length
cin>>n; //depth/height
for(int k=1; k<=n; k++)
{
for(int i=0; i<=k; i++)
{
c=c+(pow(-1, k+i)*binomialCoeff(i+2*n-2*k+1, i));
}
coefficient[k] = c;
c=0;
}
for(int j=1; j<=m/2; j++)
{
for(int i=1; i<m/2-(n-1); i++)
{
k=j-(i-1);
if(k<0) k=0;
p=p+pow(-1, i-1)*num[k]*coefficient[i];
}
num[j+1] = p;
p=0;
}
cout<<num[m/2-(n-1)];
}
// Tim C. Flowers, May 14 2018
CROSSREFS
T(2n,n) gives A268316.
Counting by leaves instead of height gives A001263.
The unordered version is A034781.
The height statistic is ranked by A358379, unordered A109082.
Sequence in context: A108625 A112857 A118801 * A343237 A094507 A065625
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)