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

A268316 a(n) is the number of Dyck paths of length 4n and height n.

Original entry on oeis.org

1, 1, 7, 57, 484, 4199, 36938, 328185, 2937932, 26457508, 239414383, 2175127695, 19827974412, 181266501290, 1661241473220, 15257624681145, 140400178555644, 1294141164447692, 11946771748196428, 110435320379615620, 1022108852175416720, 9470416604629933935

Offset: 0

Gheorghe Coserea, Feb 01 2016

Equivalently, a(n) is the number of rooted plane trees with 2n+1 nodes and height n.

			For n = 2 the a(2) = 7 solutions are
              /\/\/\       |
LLRLRLRR     /      \     /|\
................................
                /\        /|\
LRLLRRLR     /\/  \/\      |
................................
              /\  /\       /\
LLRRLLRR     /  \/  \     /  \
................................
              /\           /|\
LLRRLRLR     /  \/\/\     /
................................
                  /\      /|\
LRLRLLRR     /\/\/  \        \
................................
              /\/\         /\
LLRLRRLR     /    \/\     /\
................................
                /\/\       /\
LRLLRLRR     /\/    \       /\

Gheorghe Coserea, Table of n, a(n) for n = 0..1000.
Gheorghe Coserea, Solutions for n=3.
Gheorghe Coserea, Solutions for n=4.
Gheorghe Coserea, MiniZinc model for generating solutions.

Cf. A080936, A268315.

Column k=2 of A289481.

[Binomial(4*n, n)*2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3)): n in [1..30]]; // Vincenzo Librandi, Feb 04 2016

Table[Binomial[4 n, n] 2 (2 n + 3) (2 n^2 + 1) / ((3 n + 1) (3 n + 2) (3 n + 3)), {n, 1, 25}] (* Vincenzo Librandi, Feb 04 2016 *)
Drop[CoefficientList[Series[-((-1 + HypergeometricPFQ[{-3/4, -1/2, -1/4}, {1/3, 2/3}, 256 x/27])/(4x)) + 4/5 x HypergeometricPFQ[{5/4, 3/2, 7/4}, {7/3, 8/3}, 256 x/27] + 8/3 x^2 HypergeometricPFQ[{9/4, 5/2, 11/4}, {10/3, 11/3}, 256x/27], {x, 0, 20}], x], 1] (* Benedict W. J. Irwin, Aug 09 2016 *)

a(n) = binomial(4*n,n) * 2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3));
vector(21, i, a(i))

a(n) = T(2n,n), where T(n,k) is defined by A080936.
a(n) = binomial(4*n,n) * 2*(2*n+3)*(2*n^2+1)/((3*n+1)*(3*n+2)*(3*n+3)).
a(n) ~ K * A268315^n / sqrt(n), where K = 8/27 * sqrt(2/(3*Pi)) = 0.13649151584...
G.f.: -((3F2(-3/4, -1/2, -1/4; 1/3, 2/3; 256*x/27)-1)/(4*x)) + 4/5*x*3F2(5/4, 3/2, 7/4; 7/3, 8/3; 256*x/27) + 8/3*x^2*3F2(9/4, 5/2, 11/4; 10/3, 11/3; 256*x/27). - Benedict W. J. Irwin, Aug 09 2016
Recurrence: 3*(n+1)*(2*n + 1)*(3*n + 1)*(3*n + 2)*(2*n^2 - 4*n + 3)*a(n) = 8*(2*n - 1)*(2*n + 3)*(4*n - 3)*(4*n - 1)*(2*n^2 + 1)*a(n-1). - Vaclav Kotesovec, Aug 10 2016

Added a(0)=1, adjusted b-file - N. J. A. Sloane, Dec 22 2016

A289473 Number of Dyck paths of semilength 3*n and height n.

Original entry on oeis.org

1, 1, 31, 1341, 59917, 2665884, 117939506, 5201391077, 229151753951, 10097407871079, 445314691051823, 19662213285986440, 869281482750346782, 38482251447081815180, 1705762097183926444500, 75702251155478791228341, 3363573441149092994645423

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..604

Column k=3 of A289481.

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-> `if`(n=0, 1, b(6*n, 0, n)-b(6*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 3^(6*n + 1/2) / (2^(4*n + 9/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289474 Number of Dyck paths of semilength 4*n and height n.

Original entry on oeis.org

1, 1, 127, 26609, 5828185, 1244027317, 258054207727, 52402156308977, 10488803639337560, 2079716852900452250, 409870041643305514072, 80466951297324661639450, 15759844503630649015980996, 3082231209190859509953543989, 602325527248635884295374077954

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..400

Column k=4 of A289481.

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-> `if`(n=0, 1, b(8*n, 0, n)-b(8*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 2^(24*n + 4) / (3^(3*n + 1/2) * 5^(5*n + 7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289475 Number of Dyck paths of semilength 5*n and height n.

Original entry on oeis.org

1, 1, 511, 497845, 517884748, 517500496981, 492342898340494, 450205866074148509, 399858332322926629152, 347831920544342751131378, 298149337418229660486879546, 252909751775727886411508895575, 212950273659595164912087912232227

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..343

Column k=5 of A289481.

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-> `if`(n=0, 1, b(10*n, 0, n)-b(10*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 5^(10*n + 1/2) / (2^(4*n + 3/2) * 3^(6*n + 7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289476 Number of Dyck paths of semilength 6*n and height n.

Original entry on oeis.org

1, 1, 2047, 9096393, 44100374341, 203421120941736, 877820839402932499, 3578930527547615106601, 13968353507597683646018640, 52773530288643811045085269442, 194648265795425910705859329140951, 705285559217587334571033534680055625

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..283

Column k=6 of A289481.

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-> `if`(n=0, 1, b(12*n, 0, n)-b(12*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 2^(24*n + 7/2) * 3^(12*n + 1/2) / (5^(5*n+1/2) * 7^(7*n+7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289477 Number of Dyck paths of semilength 7*n and height n.

Original entry on oeis.org

1, 1, 8191, 164531565, 3673214880049, 77462600751077244, 1505240258416480353423, 27202373147496127842409429, 464106749942563876038980247765, 7576947003340172511554825394061140, 119634586370431286462528705183632896422

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..241

Column k=7 of A289481.

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-> `if`(n=0, 1, b(14*n, 0, n)-b(14*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 7^(14*n + 1/2) / (2^(16*n + 8) * 3^(6*n + 1/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289478 Number of Dyck paths of semilength 8*n and height n.

Original entry on oeis.org

1, 1, 32767, 2962826465, 302279227822132, 28940151142665744800, 2518778621914294827210397, 200931623862007000173683722721, 14934414860406931133627906259665137, 1050339437420146526008731445371770861951, 70783666464470090848536562606347425026054174

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..210

Column k=8 of A289481.

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-> `if`(n=0, 1, b(16*n, 0, n)-b(16*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 2^(64*n + 9/2) / (3^(18*n + 7) * 7^(7*n + 1/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289479 Number of Dyck paths of semilength 9*n and height n.

Original entry on oeis.org

1, 1, 131071, 53249182309, 24707711028329725, 10683679703096752747668, 4147304882800594101766257490, 1455763914060254648633279812633997, 470172045819740629127626302976354304026, 142143740345412121643458345045577780672138977

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..186

Column k=9 of A289481.

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-> `if`(n=0, 1, b(18*n, 0, n)-b(18*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 3^(36*n + 1) / (2^(16*n + 2)* 5^(10*n + 7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

A289480 Number of Dyck paths of semilength 10*n and height n.

Original entry on oeis.org

1, 1, 524287, 956185155129, 2011805242484811913, 3913893675608035491579363, 6753921048102794214403632812402, 10404372657815158859307324171401493273, 14572291057533118353907127088834174993619633, 18906515358804836479733610566557899759396278209535

Offset: 0

Alois P. Heinz, Jul 06 2017

nonn

In general, column k>1 of A289481 is asymptotic to 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

Alois P. Heinz, Table of n, a(n) for n = 0..167

Column k=10 of A289481.

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-> `if`(n=0, 1, b(20*n, 0, n)-b(20*n, 0, n-1)):
seq(a(n), n=0..20);

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

a(n) ~ 2^(40*n + 7/2) * 5^(20*n + 1/2) / (3^(18*n + 1) * 11^(11*n + 7/2) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 14 2017

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

A268316 a(n) is the number of Dyck paths of length 4n and height n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A289473 Number of Dyck paths of semilength 3*n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289474 Number of Dyck paths of semilength 4*n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289475 Number of Dyck paths of semilength 5*n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289476 Number of Dyck paths of semilength 6*n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289477 Number of Dyck paths of semilength 7*n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A289478 Number of Dyck paths of semilength 8*n and height n.

Views