login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126216 Triangle read by rows: T(n,k) is the number of Schroeder paths of semilength n containing exactly k peaks but no peaks at level one (n >= 1; 0 <= k <= n-1). 17
1, 2, 1, 5, 5, 1, 14, 21, 9, 1, 42, 84, 56, 14, 1, 132, 330, 300, 120, 20, 1, 429, 1287, 1485, 825, 225, 27, 1, 1430, 5005, 7007, 5005, 1925, 385, 35, 1, 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1 (list; table; graph; refs; listen; history; text; internal format)
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</a, 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)

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

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

Cf. A126182.

Cf. A086810, A126120.

Sequence in context: A123971 A060920 A107842 * A124733 A137597 A059340

Adjacent sequences:  A126213 A126214 A126215 * A126217 A126218 A126219

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Dec 20 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 23:57 EDT 2022. Contains 356016 sequences. (Running on oeis4.)