|
|
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).
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.
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
|
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)):
|
|
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)];
}
|
|
CROSSREFS
|
Counting by leaves instead of height gives A001263.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|