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.
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 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.
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
# 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
KEYWORD
nonn,tabl
AUTHOR
Henry Bottomley, Feb 25 2003
STATUS
approved