OFFSET
1,2
COMMENTS
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
LINKS
Gheorghe Coserea, Rows n = 1..200, flattened
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
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.
D. Callan, Polygon Dissections and Marked Dyck Paths
T. 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, 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.
J.-C. Novelli, J.-Y. 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.
FORMULA
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
EXAMPLE
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;
...
MAPLE
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
MATHEMATICA
Table[Binomial[n, k] Binomial[2 n - k, n + 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Jan 09 2016 *)
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Emeric Deutsch, Dec 20 2006
STATUS
approved