login
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

%I #116 Oct 09 2022 20:38:56

%S 1,2,1,5,5,1,14,21,9,1,42,84,56,14,1,132,330,300,120,20,1,429,1287,

%T 1485,825,225,27,1,1430,5005,7007,5005,1925,385,35,1,4862,19448,32032,

%U 28028,14014,4004,616,44,1,16796,75582,143208,148512,91728,34398,7644,936,54,1

%N 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 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 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 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 Mirror image of triangle A033282. - _Philippe Deléham_, Oct 20 2007

%C 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 First column (k=0) gives the Catalan numbers (A000108). - _Alexander Karpov_, Jun 10 2018

%H Gheorghe Coserea, <a href="/A126216/b126216.txt">Rows n = 1..200, flattened</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2101.06713">On the inversion of Riordan arrays</a>, arXiv:2101.06713 [math.CO], 2021.

%H 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 D. Callan, <a href="http://www.stat.wisc.edu/~callan/papers/polygon_dissections/">Polygon Dissections and Marked Dyck Paths</a>

%H T. 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 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 Rosena R. X. Du, Xiaojie Fan, 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 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 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 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 J.-C. Novelli, J.-Y. 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.

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

%F 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 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 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 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 From _Tom Copeland_, Oct 10 2011: (Start)

%F With polynomials

%F P(0,t) = 0

%F P(1,t) = 1

%F P(2,t) = 1

%F P(3,t) = 2 + t

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

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

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

%F 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 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 From _Tom Copeland_, Dec 09 2019: (Start)

%F 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 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 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 T(3,1)=5 because we have HUUDD, UUDDH, UUUDDD, UHUDD and UUDHD.

%e Triangle starts:

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

%e 1 1;

%e 2 2, 1;

%e 3 5, 5; 1;

%e 4 14, 21, 9, 1;

%e 5 42, 84, 56, 14, 1;

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

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

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

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

%e 10 ...

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

%e 1;

%e 1, 0;

%e 2, 1, 0;

%e 5, 5, 1, 0;

%e 14, 21, 9, 1, 0;

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

%e ...

%p 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 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 (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 (PARI)

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

%o concat(vector(10, n, vector(n, k, t(n,k-1)))) \\ _Gheorghe Coserea_, Apr 24 2016

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

%Y Cf. A126182.

%Y Cf. A086810, A126120, A243660, A243661.

%K nonn,tabl

%O 1,2

%A _Emeric Deutsch_, Dec 20 2006