A080936 - OEIS

%I #103 Jul 03 2024 12:46:46

%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.

%H Vince White, <a href="https://digitalcommons.georgiasouthern.edu/etd/2799">Enumeration of Lattice Paths with Restrictions</a>, (2024). Electronic Theses and Dissertations. 2799. See pp. 19, 25.

%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