|
%I #99 Nov 30 2023 10:28:44
%S 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,
%T 1,127,482,484,247,75,13,1,1,255,1341,1684,1053,410,102,15,1,1,511,
%U 3669,5661,4199,1975,629,133,17,1,1,1023,9922,18579,16017,8778,3366,912,168,19,1
%N Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1 <= k <= n).
%C Sum of entries in row n is A000108(n) (the Catalan numbers).
%C From _Gus Wiseman_, Nov 16 2022: (Start)
%C Also the number of unlabeled ordered rooted trees with n nodes and height k. For example, row n = 5 counts the following trees:
%C (oooo) ((o)oo) (((o))o) ((((o))))
%C ((oo)o) (((o)o))
%C ((ooo)) (((oo)))
%C (o(o)o) ((o(o)))
%C (o(oo)) (o((o)))
%C (oo(o))
%C ((o)(o))
%C (End)
%D 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.
%H Alois P. Heinz, <a href="/A080936/b080936.txt">Rows n = 1..141, flattened</a>
%H 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, <a href="https://arxiv.org/abs/2311.14055">Interval and L-interval Rational Parking Functions</a>, arXiv:2311.14055 [math.CO], 2023. See p. 11.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000013">The height of a Dyck path</a>
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000013">The height of a Dyck path.</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000094">The depth of an ordered tree.</a>, <a href="http://www.findstat.org/St000166">The depth minus 1 of an ordered tree</a>
%H A. Joseph and P. Lamprou, <a href="http://arxiv.org/abs/1512.00406">A new interpretation of Catalan numbers</a>, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
%H G. Kreweras, <a href="http://www.numdam.org/item?id=BURO_1970__15__3_0">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
%H G. Kreweras, <a href="/A000108/a000108_1.pdf">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
%H Kevin Limanta, Hopein Christofen Tang, and Yozef Tjandra, <a href="https://arxiv.org/abs/2105.14439">Permutation-generated maps between Dyck paths</a>, arXiv:2105.14439 [math.CO], 2021. Mentions this sequence.
%H Thomas Tunstall, Tim Rogers, and Wolfram Möbius, <a href="https://arxiv.org/abs/2303.01579">Assisted percolation of slow-spreading mutants in heterogeneous environments</a>, arXiv:2303.01579 [q-bio.PE], 2023.
%F T(n, k) = A080934(n, k) - A080934(n, k-1).
%F 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
%F 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
%F 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
%e 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
%e Triangle starts:
%e 1;
%e 1, 1;
%e 1, 3, 1;
%e 1, 7, 5, 1;
%e 1, 15, 18, 7, 1;
%e 1, 31, 57, 33, 9, 1;
%e 1, 63, 169, 132, 52, 11, 1;
%p f := proc (k) options operator, arrow:
%p sum(binomial(k-i, i)*(-z)^i, i = 0 .. floor((1/2)*k))
%p end proc:
%p h := proc (k) options operator, arrow:
%p z^k/(f(k)*f(k+1))
%p end proc:
%p T := proc (n, k) options operator, arrow:
%p coeff(series(h(k), z = 0, 25), z, n)
%p end proc:
%p for n to 11 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form _Emeric Deutsch_, Jun 08 2011
%p # second Maple program:
%p b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
%p `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
%p end:
%p T:= (n, k)-> b(2*n, 0, k) -`if`(k=0, 0, b(2*n, 0, k-1)):
%p seq(seq(T(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Aug 06 2012
%t 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_ *)
%t aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
%t Table[Length[Select[aot[n],Depth[#]-2==k&]],{n,1,9},{k,1,n-1}] (* _Gus Wiseman_, Nov 16 2022 *)
%o (C++ 11)
%o #include <iostream>
%o #include <cmath>
%o using namespace std;
%o long long b,d,c,coefficient[1000],n,m,num[1000],p=0,k;
%o int binomialCoeff(long long b, long long d)
%o {
%o if (d==0 || d==b)
%o return 1;
%o return binomialCoeff(b-1, d-1) + binomialCoeff(b-1, d);
%o }
%o int main()
%o {
%o num[1]=1;
%o cin>>m; //total length
%o cin>>n; //depth/height
%o for(int k=1; k<=n; k++)
%o {
%o for(int i=0; i<=k; i++)
%o {
%o c=c+(pow(-1,k+i)*binomialCoeff(i+2*n-2*k+1,i));
%o }
%o coefficient[k] = c;
%o c=0;
%o }
%o for(int j=1; j<=m/2; j++)
%o {
%o for(int i=1; i<m/2-(n-1); i++)
%o {
%o k=j-(i-1);
%o if(k<0) k=0;
%o p=p+pow(-1,i-1)*num[k]*coefficient[i];
%o }
%o num[j+1] = p;
%o p=0;
%o }
%o cout<<num[m/2-(n-1)];
%o }
%o // _Tim C. Flowers_, May 14 2018
%Y Cf. A000108 (row sums), A079214, A080934, A080935, A259885, A259899, A289481.
%Y Columns k=1-10 give: A000012, A000225(n-1), A258109, A262600, A289418, A289419, A289420, A289421, A289422, A289423.
%Y T(2n,n) gives A268316.
%Y Counting by leaves instead of height gives A001263.
%Y The unordered version is A034781.
%Y The height statistic is ranked by A358379, unordered A109082.
%Y Cf. A000081, A005043, A032027, A284778.
%K nonn,tabl
%O 1,5
%A _Henry Bottomley_, Feb 25 2003
|
