1,2

A Schroeder path of semilength n is a lattice path in the first quadrant, from the origin to the point (2n,0) and consisting of steps U=(1,1), D=(1,-1) and H=(2,0).

Also number of Schroeder paths of semilength n containing exactly k doublerises but no (2,0) steps at level 0 (n >= 1; 0 <= k <= n-1). Also number of doublerise-bicolored Dyck paths (doublerises come in two colors; also called marked Dyck paths) of semilength n and having k doublerises of a given color (n >= 1; 0 <= k <= n-1). Also number of 12312- and 121323-avoiding matchings on [2n] with exactly k crossings.

Essentially the triangle given by [1,1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 20 2007

Mirror image of triangle A033282. - Philippe Deléham, Oct 20 2007

For relation to Lagrange inversion, or series reversion and the geometry of associahedra, or Stasheff polytopes (and other combinatorial objects), see A133437. - Tom Copeland, Sep 29 2008

First column (k=0) gives the Catalan numbers (A000108). - Alexander Karpov, Jun 10 2018

T(n,k) is the multiplicity of the k-hook representation of the symmetric group in the (n-1)st parking space representation (see Pak and Postnikov, 1995). - Joshua Mundinger, Jul 18 2025

Gheorghe Coserea, Rows n = 1..200, flattened

Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.

D. Callan, Polygon Dissections and Marked Dyck Paths.

W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, The Electronic Journal of Combinatorics 13, 2006, #R112, Theorem 3.3.

Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015.

D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) #10.9.2.

Rosena R. X. Du, Xiaojie Fan, and Yue Zhao, Enumeration on row-increasing tableaux of shape 2 X n, arXiv:1803.01590 [math.CO], 2018.

Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.

S. Mizera, Combinatorics and Topology of Kawai-Lewellen-Tye Relations, arXiv:1706.08527 [hep-th], 2017.

Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

Jean-Christophe Novelli and Jean-Yves Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Fig. 7.

I. Pak and A. Postnikov, Enumeration of trees and one amazing representation of the symmetric group, Proceedings of the 8-th International Conference FPSAC, 1996.

Hua Xin, Lattice points of flow polytopes related to caracol graphs, AIMS Elect. Res. Archive 33(10) (2025) 6141-6175. See p. 6160.

T(n,k) = C(n,k)*C(2*n-k,n+1)/n (0 <= k <= n-1).

G.f.: G(t,z) = (1-2*z-t*z-sqrt(1-4*z-2*t*z+t^2*z^2))/(2*(1+t)*z).

Equals N * P, where N = the Narayana triangle (A001263) and P = Pascal's triangle, as infinite lower triangular matrices. A126182 = P * N. - Gary W. Adamson, Nov 30 2007

G.f.: 1/(1-x-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-.... (continued fraction). - Paul Barry, Feb 06 2009

Let h(t) = (1-t)^2/(1+(u-1)*(1-t)^2) = 1/(u + 2*t + 3*t^2 + 4*t^3 + ...), then a signed (n-1)-th row polynomial of A126216 is given by u^(2n-1)*(1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=2. The power series expansion of h(t) is related to A181289 (cf. A086810). - Tom Copeland, Oct 09 2011

From Tom Copeland, Oct 10 2011: (Start)

With polynomials

P(0,t) = 0

P(1,t) = 1

P(2,t) = 1

P(3,t) = 2 + t

P(4,t) = 5 + 5 t + t^2

P(5,t) = 14 + 21 t + 9 t^2 + t^3

The o.g.f. A(x,t) = (1+x*t-sqrt((1-x*t)^2-4x))/(2(1+t)), and

B(x,t) = x - x^2/(1-t*x) = x - x^2 - ((t*x)^3 + (t*x)^4 + ...)/t^2 is the compositional inverse in x. [series corrected by Tom Copeland, Dec 10 2019]

Let h(x,t) = 1/(dB/dx) = (1-tx)^2/(1-(t+1)(2x-tx^2)) = 1/(1 - 2x - 3tx^2 + 4t^2x^3 + ...). Then P(n,t) = (1/n!)(h(x,t)*d/dx)^n x, evaluated at x=0, A = exp(x*h(u,t)*d/du) u, evaluated at u=0, and dA/dx = h(A(x,t),t). (End)

From Tom Copeland, Dec 09 2019: (Start)

The polynomials in my 2011 formula entry above evaluate to an aerated, alternating sign sequence of the Catalan numbers A000108 with t = -2. The first few are P(2,-2) = 1, P(3,-2) = 0, P(4,t) = -1, P(5,-2) = 0, P(6,-2) = 2, P(7,-2) = 0, P(8,-2) = -5, P(9,-2) = 0, P(10,-2) = 14.

Generalizing the relations between w = theta and u = phi in Mizera on pp. 32-34, modify the inverse pair above to w = i * B(-i*u,t) = u + i * u^2/(1+i*t*u), where i is the imaginary number, and u = i*A(-i*w,t) = i*(1 - i*w*t - sqrt((1 + i*w*t)^2 + i*4*w))/(2(1+t)). Then the expression for V'(w) in Mizera generalizes to V'(w) = -i*(w - u) and reduces to V'(w) = (1 - sqrt(1-4 w^2))/2 when evaluated at t = -2, which is an o.g.f. for A126120. Cf. also A086810. (End)

Sum_{k = 0..n-1} (-1)^k*T(n,k)*binomial(x + 2*n - k, 2*n - k) = ( (x + 1) * ( Product_{k = 2..n} (x + k)^2 ) * (x + n + 1) )/(n!*(n + 1)!) for n >= 1. Cf. A243660 and A243661. - Peter Bala, Oct 08 2022

T(3,1)=5 because we have HUUDD, UUDDH, UUUDDD, UHUDD and UUDHD.

Triangle starts:

n\k 0 1 2 3 4 5 6 7 8

1 1;

2 2, 1;

3 5, 5; 1;

4 14, 21, 9, 1;

5 42, 84, 56, 14, 1;

6 132, 330, 300, 120, 20, 1;

7 429, 1287, 1485, 825, 225, 27, 1;

8 1430, 5005, 7007, 5005, 1925, 385, 35, 1;

9 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1;

10 ...

Triangle [1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,...] begins:

1;

1, 0;

2, 1, 0;

5, 5, 1, 0;

14, 21, 9, 1, 0;

42, 84, 56, 14, 1, 0;

...

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

Table[Binomial[n, k] Binomial[2 n - k, n + 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Jan 09 2016 *)

(PARI) tabl(nn) = {mP = matrix(nn, nn, n, k, binomial(n-1, k-1)); mN = matrix(nn, nn, n, k, binomial(n-1, k-1) * binomial(n, k-1) / k); mprod = mN*mP; for (n=1, nn, for (k=1, n, print1(mprod[n, k], ", "); ); print(); ); } \\ Michel Marcus, Apr 16 2015

(PARI)

t(n, k) = binomial(n, k)*binomial(2*n-k, n+1)/n;

concat(vector(10, n, vector(n, k, t(n, k-1)))) \\ Gheorghe Coserea, Apr 24 2016

Cf. A000108, A002054, A002055, A002056, A007160, A033280, A033281, A033282.

Cf. A126182.

Cf. A086810, A126120, A243660, A243661.

Sequence in context: A060920 A391610 A107842 * A124733 A137597 A059340

Adjacent sequences: A126213 A126214 A126215 * A126217 A126218 A126219

nonn,tabl

Emeric Deutsch, Dec 20 2006

approved