A268316 -id:A268316 - 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

A289481 Number A(n,k) of Dyck paths of semilength k*n and height n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 7, 1, 0, 1, 1, 31, 57, 1, 0, 1, 1, 127, 1341, 484, 1, 0, 1, 1, 511, 26609, 59917, 4199, 1, 0, 1, 1, 2047, 497845, 5828185, 2665884, 36938, 1, 0, 1, 1, 8191, 9096393, 517884748, 1244027317, 117939506, 328185, 1, 0

Offset: 0

Alois P. Heinz, Jul 06 2017

For fixed k > 1, A(n,k) ~ 2^(2*k*n + 3) * k^(2*k*n + 1/2) / ((k-1)^((k-1)*n + 1/2) * (k+1)^((k+1)*n + 7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

			Square array A(n,k) begins:
  1, 1,    1,       1,          1,            1, ...
  0, 1,    1,       1,          1,            1, ...
  0, 1,    7,      31,        127,          511, ...
  0, 1,   57,    1341,      26609,       497845, ...
  0, 1,  484,   59917,    5828185,    517884748, ...
  0, 1, 4199, 2665884, 1244027317, 517500496981, ...

Alois P. Heinz, Antidiagonals n = 0..80, flattened

Columns k=0..10 give: A000007, A000012, A268316, A289473, A289474, A289475, A289476, A289477, A289478, A289479, A289480.
Rows n=0-2 give: A000012, A057427, A083420(k+1).
Main diagonal gives A289482.
Cf. A080936.

b:= proc(x, y, k) option remember;
      `if`(x=0, 1, `if`(y>0, b(x-1, y-1, k), 0)+
      `if`(y <  min(x-1, k), b(x-1, y+1, k), 0))
    end:
A:= (n, k)-> `if`(n=0, 1, b(2*n*k, 0, n)-b(2*n*k, 0, n-1)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[x_, y_, k_]:=b[x, y, k]=If[x==0, 1, If[y>0, b[x - 1, y - 1, k], 0] + If[yIndranil Ghosh, Jul 07 2017, after Maple code *)

A268315 Decimal expansion of 256/27.

Original entry on oeis.org

9, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8, 1, 4, 8

Offset: 1

Gheorghe Coserea, Feb 01 2016

			9.481481481481481481481481481481...

Exponential growth rate for A000260, A002293, A005810, A006633, A006634, A052203, A066381, A069271, A078516, A078995, A153396, A196678, A268316.

[9] cat &cat[[4, 8, 1]^^45]; // Vincenzo Librandi, Feb 04 2016

Join[{9}, PadRight[{}, 120, {4, 8, 1}]] (* Vincenzo Librandi, Feb 04 2016 *)

PARI
```
1.0 * 256/27
```

More digits from Jon E. Schoenfield, Mar 15 2018

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

A289481 Number A(n,k) of Dyck paths of semilength k*n and height n; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A268315 Decimal expansion of 256/27.

Views

Author

Keywords

Examples

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions