A003516 -id:A003516 - cp's OEIS frontend

A114492 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having k DDUU's, where U=(1,1), D=(1,-1) (0<=k<=floor(n/2)-1 for n>=2).

1, 1, 2, 5, 13, 1, 35, 7, 97, 34, 1, 275, 143, 11, 794, 558, 77, 1, 2327, 2083, 436, 16, 6905, 7559, 2180, 151, 1, 20705, 26913, 10051, 1095, 22, 62642, 94547, 43796, 6758, 268, 1, 190987, 328943, 183130, 37402, 2409, 29, 586219, 1136218, 742253, 191408

Offset: 0

Emeric Deutsch, Dec 01 2005

Rows 0 and 1 contain one term each; row n contains floor(n/2) terms (n>=2).
Row sums are the Catalan numbers (A000108). Column 0 yields A086581.
Sum(k*T(n,k),k=0..floor(n/2)-1) = binomial(2n-3,n-4) (A003516).

			T(5,1) = 7 because we have UU(DDUU)DUDD, UU(DDUU)UDDD, UDUU(DDUU)DD, their mirror images and UUU(DDUU)DDD (the DDUU's are shown between parentheses).
Triangle starts:
   1;
   1;
   2;
   5;
  13,  1;
  35,  7;
  97, 34, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See p. 12.
FindStat - Combinatorial Statistic Finder, The number of occurrences of the contiguous pattern [.,[.,[[.,.],.]]].
Toufik Mansour and Mark Shattuck, Counting occurrences of subword patterns in non-crossing partitions, Art Disc. Appl. Math. (2022).
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A086581, A003516.

G:=1/2/(-t*z-z^2+z^2*t)*(-1+2*z-2*t*z-z^2+z^2*t+sqrt(1+z^4-2*z^4*t+z^4*t^2-4*z+2*z^2-2*z^2*t)): Gser:=simplify(series(G,z=0,17)): P[0]:=1: for n from 1 to 14 do P[n]:=coeff(Gser,z^n) od: 1; 1; for n from 0 to 14 do seq(coeff(t*P[n],t^j),j=1..floor(n/2)) od; # yields sequence in triangular form

m = 15; G[, ] = 0;
Do[G[t_, z_] = (-1 + z - t z - t z G[t, z]^2 - z^2 G[t, z]^2 + t z^2 G[t, z]^2)/(-1 + 2z - 2t z - z^2 + t z^2) + O[t]^Floor[m/2] + O[z]^m, {m}];
CoefficientList[#, t]& /@ Take[CoefficientList[G[t, z], z], m] // Flatten (* Jean-François Alcover, Oct 05 2019 *)

G.f.: G=G(t, z) satisfies z(t+z-tz)G^2-(1-2(1-t)z+(1-t)z^2)G+1-z+tz=0.

A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.

Original entry on oeis.org

0, 0, 0, 0, 1, 8, 44, 209, 924, 3927, 16303, 66691, 270181, 1087371, 4356131, 17394026, 69289961, 275543036, 1094352236, 4342295396, 17218070066, 68239187876, 270351828476, 1070824260326, 4240695090452, 16792454677874, 66492351226050, 263285419856250, 1042540731845950

Offset: 0

Stefano Spezia, Apr 14 2024

nonn

			a(4) = 1 because there is 1 Catalan word of length 4 with one valley: 0101.
a(5) = 8 because there are 8 Catalan words of length 5 with one valley: 00101, 01010, 01011, 01012, 01101, 01201, and 01212 (see Figure 9 at p. 14 in Baril et al.).

Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See Corollary 4.5, p. 15.

Cf. A371964, A371965.

Cf. A003516.

a:= proc(n) option remember; `if`(n<4, 0,
      a(n-1)+binomial(2*n-3, n-4))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Apr 15 2024

CoefficientList[Series[(1 - 5x+5x^2-(1-3x+x^2)Sqrt[1-4x])/(2(1-x)x Sqrt[1-4x]),{x,0,28}],x]

from math import comb
def A371963(n): return sum(comb((n-i<<1)-3,n-i-4) for i in range(n-3)) # Chai Wah Wu, Apr 15 2024

G.f.: (1-5*x+5*x^2-(1-3*x+x^2)*sqrt(1-4*x))/(2*(1-x)*x*sqrt(1-4*x)).
a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-3).
a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).
a(n) - a(n-1) = A003516(n-2).

A101282 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k valleys.

Original entry on oeis.org

2, 5, 1, 14, 7, 1, 42, 36, 11, 1, 132, 165, 80, 16, 1, 429, 715, 484, 155, 22, 1, 1430, 3003, 2639, 1183, 273, 29, 1, 4862, 12376, 13468, 7840, 2554, 448, 37, 1, 16796, 50388, 65688, 47328, 20124, 5031, 696, 46, 1, 58786, 203490, 310080, 267444, 141219, 46377, 9230, 1035, 56, 1

Offset: 1

Emeric Deutsch, Dec 20 2004

A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis (Schroeder paths are counted by the large Schroeder numbers (A006318)). Also number of Schroeder paths of length 2n and having k UU's. Also number of Schroeder paths of length 2n and having k peaks at height >1,

			T(3,1) = 7 because we have HU(DU)D, U(DU)DH, U(DU)HD, UH(DU)D, U(DU)UDD, UUD(DU)D and UU(DU)DD, the valleys being shown between parentheses.
Triangle begins:
    2;
    5,   1;
   14,   7,  1;
   42,  36, 11,  1;
  132, 165, 80, 16, 1;
  ...

Alois P. Heinz, Rows n = 1..150, flattened
Wikipedia, Schröder number

Row sums give A006318.
T(2n,n) gives A385299.
Cf. A000108, A003516, A060693.

G := 1/2/(-t*z-z^2+z^2*t)*(-1+2*z-t*z+sqrt(1-4*z-2*t*z+t^2*z^2)):Gser:=simplify(series(G,z=0,13)):for n from 1 to 11 do P[n]:=coeff(Gser,z^n) od: for n from 1 to 11 do seq(coeff(t*P[n],t^k),k=1..n) od; # yields the sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y-1, 1)+b(x-1, y+1, 0)*z^t+b(x-2, y, 0))))
    end:
T:= (n, k)-> coeff(b(2*n, 0$2), z, k):
seq(seq(T(n,k), k=0..n-1), n=1..12);  # Alois P. Heinz, Jun 17 2025

T(n,m):=if n=0 or m=0 then 0 else if m=1 then 1/(n+1)*binomial(2*n+2,n) else  sum(((k+1)*binomial(n-k,m-1)*binomial(2*n-m-k+1,n+1))/(n-k),k,0,n-m); /* Vladimir Kruchinin, Oct 14 2020 */

G.f.: G=G(t, z) satisfies z(t+z-tz)G^2-(1-2z+tz)G+1=0.
T(n,m) = Sum_{k=0..n-m} (k+1)*C(n-k,m-1)*C(2*n-m-k+1,n+1)/(n-k), m>1,  T(n,1) = 1/(n+1)*binomial(2*n+2,n).  - Vladimir Kruchinin, Oct 14 2020
From Mikhail Kurkov, Jun 17 2025: (Start)
Conjecture: The n-th row polynomial is R(n+1,0) where
  R(n,n) = 1,
  R(n,0) = Sum_{j=0..n-1} R(n-1,j) for n > 0,
  R(n,k) = R(n-1,k-1) + (x+1) * (R(n,0) - Sum_{j=0..k-1} R(n-1,j)) for 0 < k < n. (End)

A127529 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

Original entry on oeis.org

1, 1, 2, 4, 1, 8, 5, 1, 16, 17, 8, 1, 32, 49, 38, 12, 1, 64, 129, 141, 77, 17, 1, 128, 321, 453, 361, 143, 23, 1, 256, 769, 1326, 1399, 834, 247, 30, 1, 512, 1793, 3640, 4776, 3869, 1765, 402, 38, 1, 1024, 4097, 9539, 14911, 15353, 9722, 3469, 623, 47, 1, 2048, 9217

Offset: 0

Emeric Deutsch, Jan 18 2007

In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length.
Rows 0 and 1 have one term each; row n (n >= 2) has n-1 terms.
Row sums are the Catalan numbers (A000108).
T(n,0) = A011782(n).
T(n,1) = A000337(n-2).
Sum_{k>=0} k*T(n,k) = binomial(2n-1, n-3) = A003516(n-1) for n >= 3.
The distribution of the statistic "number of jumps" is given in A091894. The average jump distance in all ordered trees with n edges is 2 - 5/(n+2) (i.e., about 2 levels for n large). The Krandick reference considers jump-length for full binary trees.
Also the number of Dyck n-paths with k valleys at height >= 1. - David Scambler, Sep 01 2011
Triangle T(n,k), with zeros omitted, given by (1,1,0,1,0,1,0,1,0,1,0,1,...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 06 2012

			Triangle starts:
   1;
   1;
   2;
   4,  1;
   8,  5,  1;
  16, 17,  8,  1;
  32, 49, 38, 12, 1;
Triangle (1,1,0,1,0,1,0,1,0,1, ...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,...) begins:
   1;
   1,   0;
   2,   0,   0;
   4,   1,   0,  0;
   8,   5,   1,  0,  0;
  16,  17,   8,  1,  0, 0;
  32,  49,  38, 12,  1, 0, 0;
  64, 129, 141, 77, 17, 1, 0, 0; ... - _Philippe Deléham_, Feb 06 2012

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see Table 2).
FindStat - Combinatorial Statistic Finder, The number of valleys not on the x-axis of a Dyck path.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Cf. A000108, A000337, A003516, A011782, A091894.

G:=1/2/(1-2*z-t+t*z)*(-2*t+1+t*z-z+sqrt(-2*t*z+1-2*z+t^2*z^2-2*t*z^2+z^2)): Gser:=simplify(series(G,z=0,13)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) od: 1;1;for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

n = 12; g[t_, z_] := 1/2/(1 - 2z - t + t*z)*(-2t + 1 + t*z - z + Sqrt[-2t*z + 1 - 2z + t^2*z^2 - 2t*z^2 + z^2]); Flatten[ CoefficientList[#, t]&  /@ CoefficientList[ Simplify[Series[g[t, z], {z, 0, n}]], z]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)

T(n,m):=if n=0 and m=0 then 1 else if n=0 then 0 else sum(k*binomial(n,m+k)*binomial(n-k-1,m),k,0,n-m)/(n); /* Vladimir Kruchinin, Oct 29 2020 */

G.f.: G=G(t,z) satisfies (1 - t - 2*z + t*z)*G^2 - (1 - 2*t - z + t*z)*G - t = 0.

T(n,m) = Sum_{k=0..n-m} k*C(n,m+k)*C(n-k-1,m)/n, n>0, T(0,0)=1. - Vladimir Kruchinin, Oct 29 2020

A126325 Triangle read by rows: T(n,k) = binomial(2*n+1, n-k) (1 <= k <= n).

Original entry on oeis.org

1, 5, 1, 21, 7, 1, 84, 36, 9, 1, 330, 165, 55, 11, 1, 1287, 715, 286, 78, 13, 1, 5005, 3003, 1365, 455, 105, 15, 1, 19448, 12376, 6188, 2380, 680, 136, 17, 1, 75582, 50388, 27132, 11628, 3876, 969, 171, 19, 1, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1

Offset: 1

Emeric Deutsch, Mar 11 2007

T(n,k) is the total area between the lines y=k-1 and y=k in all Dyck paths of semilength n (1 <= k <= n).
With row and column indices starting at 0, this triangle is the Riordan array ( c(x)^4/(2 - c(x)), x*c^2(x) ), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Mar 12 2022
Equals A111418 when k starts at 0. - Georg Fischer, Jul 26 2023

			Triangle begins:
     1;
     5,    1;
    21,    7,    1;
    84,   36,    9,    1;
   330,  165,   55,   11,    1;
  1287,  715,  286,   78,   13,    1;
  5005, 3003, 1365,  455,  105,   15,    1;
  ..

G. C. Greubel, Rows n = 1..100 of triangle, flattened

Cf. A000108, A008549, A002054, A003516, A030053, A030054, A030055, A111418.

T:=Flat(List([1..10],n->List([1..n],k->Binomial(2*n+1,n-k)))); # Muniru A Asiru, Oct 24 2018

[[Binomial(2*n+1, n-k): k in [1..n]]: n in [1..15]]; // G. C. Greubel, Oct 23 2018

T:=(n,k)->binomial(2*n+1,n-k): for n from 1 to 11 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

t[n_, k_] := Binomial[2n + 1, n - k]; Table[ t[n, k], {n, 10}, {k, n}] // Flatten

for(n=1,15, for(k=1,n, print1(binomial(2*n+1, n-k), ", "))) \\ G. C. Greubel, Oct 23 2018

T(n,k) = T(n-1,k-1) + 2*T(n-1,k) + T(n-1,k+1) for n >= 2, k >= 2.
T(n,1) = A002054(n); T(n,2) = A003516(n); T(n,3) = A030053(n);
T(n,4) = A030054(n); T(n,5) = A030055(n).
Row sums yield A008549.

A216318 Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.

Original entry on oeis.org

0, 1, 2, 8, 31, 119, 456, 1749, 6721, 25883, 99892, 386308, 1496782, 5809478, 22584160, 87922215, 342741285, 1337698515, 5226732060, 20442936360, 80031775890, 313585934610, 1229695855440, 4825705232010, 18950613058026, 74467158658974, 292797216620776, 1151895428382104

Offset: 0

David Scambler, Sep 03 2012

nonn

			The 5 Dyck 3-paths after changing DU to UD become two copies of UUUDDD with one peak each and three copies of UUDUDD with two peaks each giving a(3)=8.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A001700, A003516, A005891.

CoefficientList[Series[(16*x*(1+Sqrt[1-4*x]+(5+3*Sqrt[1-4*x]-2*x)*(-1+x) x))/((1+Sqrt[1-4*x])^5*Sqrt[1-4*x]),{x,0,27}],x]

a(n):=if n<2 then n else binomial(2*n-2,n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)); /* Vladimir Kruchinin, Oct 30 2020 */

x='x+O('x^50); concat([0], Vec((16*x*(1+sqrt(1-4*x)-(5+3*sqrt(1-4*x)-2*x)*(1-x)*x)) / ((1+sqrt(1-4*x))^5*sqrt(1-4*x)))) \\ G. C. Greubel, Apr 01 2017

a(0)=0, a(1)=1, a(n>=2) = A001700(n-1) - Sum_{k=0..n-3} A001700(k) + Sum_{k=0..n-2} A003516(k) - 1.
G.f.: (16*x*(1+sqrt(1-4*x)+(5+3*sqrt(1-4*x)-2*x) * (-1+x)*x)) / ((1+sqrt(1-4*x))^5 * sqrt(1-4*x)).
a(n) ~ 5*2^(2*n-3)/sqrt(Pi*n). - Vaclav Kotesovec, Mar 21 2014
a(n) = C(2*n-2,n-1)*(5*(n-1)^2+5*(n-1)+2)/(2*n*(n+1)), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 30 2020

A085391 Square array of centered numbers, read by antidiagonals.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 4, 5, 1, 0, 1, 5, 10, 7, 1, 0, 1, 6, 15, 19, 9, 1, 0, 1, 7, 21, 35, 31, 11, 1, 0, 1, 8, 28, 56, 69, 46, 13, 1, 0, 1, 9, 36, 84, 126, 121, 64, 15, 1, 0, 1, 10, 45, 120, 210, 251, 195, 85, 17, 1, 0, 1, 11, 55, 165, 330, 462, 456, 295, 109, 19, 1, 0

Offset: 0

Paul Barry, Jul 02 2003

			Rows begin
0 0 0 0 0 0 ...
1 1 1 1 1 1 ...
1 3 5 7 9 11 ...
1 4 10 19 31 46 ...
1 5 15 35 69 121...

Rows include A005408, A005448, A005894, A008498, A008499, A008500, A008501.

Diagonals include A030662, A001700, A001791, A002054, A002694, A003516.

Square array T(n, k)=C(n+k, k)-C(n, k).

Row k has g.f. (1-x^k)/(1-x)^(k+1).

cp's OEIS Frontend

A114492 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having k DDUU's, where U=(1,1), D=(1,-1) (0<=k<=floor(n/2)-1 for n>=2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A101282 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k valleys.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Maxima

Formula

A127529 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A126325 Triangle read by rows: T(n,k) = binomial(2*n+1, n-k) (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

A216318 Number of peaks in all Dyck n-paths after changing each valley to a peak by the transform DU -> UD.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A085391 Square array of centered numbers, read by antidiagonals.

Views

Author