

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<=n1).


8



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
(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<=n1). Also number of doublerisebicolored Dyck paths (doublerises come in two colors; called also marked Dyck paths) of semilength n and having k doublerises of a given color (n>=1; 0<=k<=n1). Also number of 12312 and 121323avoiding 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]


LINKS

Table of n, a(n) for n=1..54.
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
JeanChristophe Novelli and JeanYves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959, 2012.
J.C. Novelli, J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv preprint arXiv:1403.5962, 2014. See Fig. 7.


FORMULA

T(n,k) = C(n,k)*C(2*nk,n+1)/n (0<=k<=n1).
G.f.: G(t,z)=(12*zt*zsqrt(14*z2*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/(1x(x+xy)/(1xy/(1(x+xy)/(1xy/(1(x+xy)/(1xy/(1.... (continued fraction). [Paul Barry, Feb 06 2009]
Let h(t) = (1t)^2/(1+(u1)*(1t)^2) = 1/(u+2*t+3*t^2+4*t^3+...), then a signed (n1)th row polynomial of A126216 is given by u^(2n1)*(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*tsqrt[(1x*t)^24x]}/[2(1+t)], and
B(x,t)=xx^2/(1t*x)=xx^2((t*x)^3+(t*x)^4+...) is the compositional inverse in x. (series corrected by Tom Copeland, Sep 16 2014)
Let h(x,t)= 1/(dB/dx)= (1tx)^2/[1(t+1)(2xtx^2)] =1/[12x3tx^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)


EXAMPLE

T(3,1)=5 because we have HUUDD, UDHH, UUUDDD, UHUDD and UUDHD.
Triangle starts:
1;
2,1;
5,5,1;
14,21,9,1;
42,84,56,14,1;
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*nk, n+1)/n: for n from 1 to 11 do seq(T(n, k), k=0..n1) od; # yields sequence in triangular form


CROSSREFS

Cf. A000108, A002054, A002055, A002056, A007160, A033280, A033281.
Cf. A126182.
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



