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).
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
Offset: 1
Examples
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; ...
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
- Tom 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, and 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.
- Jean-Christophe Novelli and Jean-Yves 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.
- I. Pak and A. Postnikov, Enumeration of trees and one amazing representation of the symmetric group, Proceedings of the 8-th International Conference FPSAC, 1996.
Crossrefs
Programs
-
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 *) -
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
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
Comments