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
Alois P. Heinz, Rows n = 1..141, flattened
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.
Danai Deligeorgaki and Krishna Menon, How to bounce your canon permutation, arXiv:2603.22565 [math.CO], 2026. See p. 11.
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
Ryota Inagaki and Dimana Pramatarova, On Weighted and Bounded Multidimensional Catalan Numbers, arXiv:2510.14956 [math.CO], 2025. See p. 10.
Ryota Inagaki and Dimana Pramatarova, On Semisymmetric Height and a Multidimensional Generalization of Weighted Catalan Numbers, arXiv:2604.04900 [math.CO], 2026. See pp. 4, 26.
Anthony Joseph and Polyxeni Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
Germain 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.
Shuzhen Lv, Sergey Kitaev, and Philip B. Zhang, Catalan structures arising from pattern-avoiding Stoimenow matchings and other Fishburn objects, arXiv:2509.09115 [math.CO], 2025. See p. 17.
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 13.
Thomas Tunstall, Tim Rogers, and Wolfram Möbius, Assisted percolation of slow-spreading mutants in heterogeneous environments, arXiv:2303.01579 [q-bio.PE], 2023.
Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 19, 25.
FORMULA
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
# Alternative:
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++)
#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
KEYWORD
nonn,tabl
AUTHOR
Henry Bottomley, Feb 25 2003
STATUS
approved
