A289419 -id:A289419 - cp's OEIS frontend

A080936 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1 <= k <= n).

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

Offset: 1

Henry Bottomley, Feb 25 2003

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)

			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;

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.

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

Cf. A000108 (row sums), A079214, A080934, A080935, A259885, A259899, A289481.
Columns k=1-10 give: A000012, A000225(n-1), A258109, A262600, A289418, A289419, A289420, A289421, A289422, A289423.
T(2n,n) gives A268316.
Counting by leaves instead of height gives A001263.
The unordered version is A034781.
The height statistic is ranked by A358379, unordered A109082.
Cf. A000081, A005043, A032027, A284778.

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

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 *)

T(n, k) = A080934(n, k) - A080934(n, k-1).
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

A359311 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps which reach at least 6 at some point.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 12, 89, 528, 2755, 13244, 60214, 263121, 1116791, 4637476, 18936940, 76327705, 304520286, 1205152900, 4738962369, 18540020091, 72240167011, 280579954028, 1087033982059, 4203231136230, 16228518078010, 62588797371361, 241198478726775

Offset: 0

Greg Dresden, Jan 21 2023

a(n) = A000108(n) - A080937(n), which is #(Catalan paths) - #(Catalan paths of height <= 5).

			a(n) = 0 for n <= 5 because no path of length <= 10 can reach 6 and then descend to 0.
a(6) = 1 because there is one path of length 12 that reaches 6: six steps up, and six steps back down.

Cf. A000108, A080936, A080937, A289419.

a:= n-> binomial(2*n, n)/(n+1)-(<<0|1|0>,
        <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 21 2023

Table[Sum[Binomial[2(n + 1), (n + 1) + 7 k] - 4 Binomial[2n, n + 7k], {k,1,n}], {n,0,30}]

a(n) = Sum_{k >= 1} binomial(2*(n+1), (n+1) + 7*k) - 4*binomial(2*n, n+7*k).
From Alois P. Heinz, Jan 21 2023: (Start)
G.f.: (1-sqrt(1-4*x))/(2*x) - (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3).
a(n) = Sum_{k=6..n} A080936(n,k). (End)
D-finite with recurrence -(n+1)*(n-6)*a(n) +3*(3*n^2-17*n+4)*a(n-1) +2*(-13*n^2+80*n-87)*a(n-2) +(25*n^2-161*n+246)*a(n-3) -2*(n-3)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

cp's OEIS Frontend

A080936 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula