cp's OEIS Frontend

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

%I A126216 #124 Jul 23 2025 00:10:38
%S A126216 1,2,1,5,5,1,14,21,9,1,42,84,56,14,1,132,330,300,120,20,1,429,1287,
%T A126216 1485,825,225,27,1,1430,5005,7007,5005,1925,385,35,1,4862,19448,32032,
%U A126216 28028,14014,4004,616,44,1,16796,75582,143208,148512,91728,34398,7644,936,54,1
%N 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).
%C A126216 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).
%C A126216 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.
%C A126216 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
%C A126216 Mirror image of triangle A033282. - _Philippe Deléham_, Oct 20 2007
%C A126216 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
%C A126216 First column (k=0) gives the Catalan numbers (A000108). - _Alexander Karpov_, Jun 10 2018
%C A126216 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
%H A126216 Gheorghe Coserea, <a href="/A126216/b126216.txt">Rows n = 1..200, flattened</a>
%H A126216 Paul Barry, <a href="https://arxiv.org/abs/2101.06713">On the inversion of Riordan arrays</a>, arXiv:2101.06713 [math.CO], 2021.
%H A126216 W. Y. C. Chen, T. Mansour and S. H. F. Yan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r112">Matchings avoiding partial patterns</a>, The Electronic Journal of Combinatorics 13, 2006, #R112, Theorem 3.3.
%H A126216 D. Callan, <a href="http://www.stat.wisc.edu/~callan/papers/polygon_dissections/">Polygon Dissections and Marked Dyck Paths</a>
%H A126216 Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/12/21/generators-inversion-and-matrix-binomial-and-integral-transforms/">Generators, Inversion, and Matrix, Binomial, and Integral Transforms</a>, 2015.
%H A126216 D. Drake, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Drake/drake.html">Bijections from Weighted Dyck Paths to Schröder Paths</a>, J. Int. Seq. 13 (2010) #10.9.2.
%H A126216 Rosena R. X. Du, Xiaojie Fan, and Yue Zhao, <a href="https://arxiv.org/abs/1803.01590">Enumeration on row-increasing tableaux of shape 2 X n</a>, arXiv:1803.01590 [math.CO], 2018.
%H A126216 Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.
%H A126216 S. Mizera, <a href="https://arxiv.org/abs/1706.08527">Combinatorics and Topology of Kawai-Lewellen-Tye Relations</a>, arXiv:1706.08527 [hep-th], 2017.
%H A126216 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/1209.5959">Duplicial algebras and Lagrange inversion</a>, arXiv preprint arXiv:1209.5959 [math.CO], 2012.
%H A126216 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Fig. 7.
%H A126216 I. Pak and A. Postnikov, <a href="https://fpsac-archive.github.io/FPSAC96/ARTICLES/38Pak.pdf">Enumeration of trees and one amazing representation of the symmetric group</a>, Proceedings of the 8-th International Conference FPSAC, 1996.
%F A126216 T(n,k) = C(n,k)*C(2*n-k,n+1)/n (0 <= k <= n-1).
%F A126216 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).
%F A126216 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
%F A126216 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
%F A126216 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
%F A126216 From _Tom Copeland_, Oct 10 2011: (Start)
%F A126216 With polynomials
%F A126216 P(0,t) = 0
%F A126216 P(1,t) = 1
%F A126216 P(2,t) = 1
%F A126216 P(3,t) = 2 + t
%F A126216 P(4,t) = 5 + 5 t + t^2
%F A126216 P(5,t) = 14 + 21 t + 9 t^2 + t^3
%F A126216 The o.g.f. A(x,t) = (1+x*t-sqrt((1-x*t)^2-4x))/(2(1+t)), and
%F A126216 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]
%F A126216 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)
%F A126216 From _Tom Copeland_, Dec 09 2019: (Start)
%F A126216 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.
%F A126216 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)
%F A126216 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
%e A126216 T(3,1)=5 because we have HUUDD, UUDDH, UUUDDD, UHUDD and UUDHD.
%e A126216 Triangle starts:
%e A126216    n\k  0      1      2      3      4     5    6   7  8
%e A126216    1    1;
%e A126216    2    2,     1;
%e A126216    3    5,     5;     1;
%e A126216    4   14,    21,     9,     1;
%e A126216    5   42,    84,    56,    14,     1;
%e A126216    6  132,   330,   300,   120,    20,    1;
%e A126216    7  429,  1287,  1485,   825,   225,   27,   1;
%e A126216    8 1430,  5005,  7007,  5005,  1925,  385,  35,  1;
%e A126216    9 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1;
%e A126216   10 ...
%e A126216 Triangle [1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,...] begins:
%e A126216    1;
%e A126216    1,  0;
%e A126216    2,  1,  0;
%e A126216    5,  5,  1,  0;
%e A126216   14, 21,  9,  1,  0;
%e A126216   42, 84, 56, 14,  1,  0;
%e A126216   ...
%p A126216 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
%t A126216 Table[Binomial[n, k] Binomial[2 n - k, n + 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* _Michael De Vlieger_, Jan 09 2016 *)
%o A126216 (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
%o A126216 (PARI)
%o A126216 t(n,k) = binomial(n,k)*binomial(2*n-k,n+1)/n;
%o A126216 concat(vector(10, n, vector(n, k, t(n,k-1))))  \\ _Gheorghe Coserea_, Apr 24 2016
%Y A126216 Cf. A000108, A002054, A002055, A002056, A007160, A033280, A033281, A033282.
%Y A126216 Cf. A126182.
%Y A126216 Cf. A086810, A126120, A243660, A243661.
%K A126216 nonn,tabl
%O A126216 1,2
%A A126216 _Emeric Deutsch_, Dec 20 2006