login
Triangle read by rows: T(n,k) is number of Motzkin paths of length n and having k horizontal steps.
22

%I #109 Jan 31 2024 16:40:35

%S 1,0,1,1,0,1,0,3,0,1,2,0,6,0,1,0,10,0,10,0,1,5,0,30,0,15,0,1,0,35,0,

%T 70,0,21,0,1,14,0,140,0,140,0,28,0,1,0,126,0,420,0,252,0,36,0,1,42,0,

%U 630,0,1050,0,420,0,45,0,1,0,462,0,2310,0,2310,0,660,0,55,0,1,132,0,2772,0

%N Triangle read by rows: T(n,k) is number of Motzkin paths of length n and having k horizontal steps.

%C Row sums are the Motzkin numbers (A001006). Column 0 gives the aerated Catalan numbers (A000108).

%C Let P_n(x) = Sum_{k=0..n} T(n,k)*x^k. P_0(x) = 1, P_1(x) = x, P_n(x) = x*P_(n-1)(x) + Sum_{j=0..n-2} P_j(x)*P_(n-2-j)(x); essentially the same as A124027. - _Philippe Deléham_, Oct 03 2007

%C G. J. Chaitin's numbers of s-expressions of size n are given by the coefficients of polynomials p(k, x) satisfying: p(k, x) = Sum_{j=2..k-1} p(j, x)*p(k-j, x). The coefficients of these polynomials also give (essentially) the triangle shown here. - _Roger L. Bagula_, Oct 31 2006

%C Exponential Riordan array [Bessel_I(1,2x)/x,x]. - _Paul Barry_, Mar 24 2010

%C Diagonal sums are the aerated large Schroeder numbers. - _Paul Barry_, Apr 21 2010

%C Non-vanishing antidiagonals are rows of A060693. - _Tom Copeland_, Feb 03 2016

%C These polynomials are related to the Gegenbauer polynomials which in turn are specializations of the Jacobi polynomials. The o.g.f. of the Gegenbauer polynomials is 1 / [1-2tx+x^2]^a. For the generating function Gb(x,h1,h2,a) = [x / (1 + h1 x + h2 x^2)]^a, the compositional inverse in x is Gbinv(x,h1,h2,a) = [(1-h1*y) - sqrt[(1-h1*y)^2-4h2*y^2]]/(2*h2*y) with y = x^(1/a). The polynomials of this entry are generated by Gbinv(x,t,1,1). The Legendre polynomials are related to the o.g.f. Gb(x,-2t,1,1/2). Cf. A121448. - _Tom Copeland_, Feb 07 2016

%C The bivariate o.g.f. in Copeland's Jan 29 2016 formulas can be related to conformal mappings of the complex plane and a solution of the dKP hierarchy. Cf. p. 24 of the Takebe et al. paper. - _Tom Copeland_, May 30 2018

%D G. J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987, page 169.

%H Peter J. C. Moses, <a href="/A097610/b097610.txt">Table of n, a(n) for n = 0..1080</a>

%H N. Alexeev, J. Andersen, R. Penner, and P. Zograf, <a href="http://arxiv.org/abs/1307.0967">Enumeration of chord diagrams on many intervals and their non-orientable analogs</a>, arXiv:1307.0967 [math.CO], 2013-2014.

%H M. Artioli, G. Dattoli, S. Licciardi, and S. Pagnutti, <a href="https://arxiv.org/abs/1703.07262">Motzkin Numbers: an Operational Point of View</a>, arXiv:1703.07262 [math.CO], 2017, (reverse of Table 1 on p. 3).

%H Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

%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 Paul Barry, <a href="https://arxiv.org/abs/2101.10218">On the duals of the Fibonacci and Catalan-Fibonacci polynomials and Motzkin paths</a>, arXiv:2101.10218 [math.CO], 2021.

%H Tom Copeland, <a href="http://tcjpn.wordpress.com/2015/10/12/the-elliptic-lie-triad-kdv-and-ricattt-equations-infinigens-and-elliptic-genera/">The Elliptic Lie Triad: Riccati and KdV Equations, Infinigens, and Elliptic Genera</a>

%H Colin Defant, <a href="http://arxiv.org/abs/1604.01723">Postorder Preimages</a>, arXiv preprint arXiv:1604.01723 [math.CO], 2016.

%H G. Ellingsrud, <a href="http://www.uio.no/studier/emner/matnat/math/MAT4250/h14/ell1.pdf">Elliptic curves--Basics</a>, course notes, Fall 2014.

%H P. Landweber, D. Ravenel, and R. Stong, <a href="https://www.math.rochester.edu/people/faculty/doug/mypapers/lrs.pdf">Periodic cohomology theories defined by elliptic curves</a>

%H Piera Manara and Claudio Perelli Cippo, <a href="http://www.mat.unisi.it/newsito/puma/public_html/22_2/manara_perelli-cippo.pdf">The fine structure of 4321 avoiding involutions and 321 avoiding involutions</a>, PU. M. A. Vol. 22 (2011), 227-238. - From _N. J. A. Sloane_, Oct 13 2012

%H T. Takebe, Lee-Peng Teo, and A. Zabrodin, <a href="https://arxiv.org/abs/math/0605161">Löwner equations and dispersionless hierarchies</a>, arXiv:math/0605161 [math.CV], p. 24, 2006.

%F G.f.: [1-tz-sqrt(1-2tz+t^2*z^2-4z^2)]/(2z^2).

%F T(n, k) = n!/[k!((n-k)/2)!((n-k)/2-1)! ] = A055151(n, (n-k)/2) if n-k is a nonnegative even number; otherwise T(n, k) = 0.

%F T(n, k) = C(n, k)*C((n-k)/2)*(1+(-1)^(n-k))/2 if k <= n, 0 otherwise. - _Paul Barry_, May 18 2005

%F T(n,k) = A121448(n,k)/2^k. - _Philippe Deléham_, Aug 17 2006

%F Sum_{k=0..n} T(n,k)*2^k = A000108(n+1). - _Philippe Deléham_, Aug 22 2006

%F Sum_{k=0..n} T(n,k)*3^k = A002212(n+1). - _Philippe Deléham_, Oct 03 2007

%F G.f.: 1/(1-x*y-x^2/(1-x*y-x^2/(1-x*y-x^2/.... (continued fraction). - _Paul Barry_, Dec 15 2008

%F Sum_{k=0..n} T(n,k)*4^k = A005572(n). - _Philippe Deléham_, Dec 03 2009

%F T(n,k) = A007318(n,k)*A126120(n-k). - _Philippe Deléham_, Dec 12 2009

%F From _Tom Copeland_, Jan 23 2016: (Start)

%F E.g.f.: M(x,t) = e^(xt) AC(t) = e^(xt) I_1(2t)/t = e(xt) * e.g.f.(A126120(t)) = e^(xt) Sum_{n>=0} t^(2n)/(n!(n+1)!) = exp[t P(.,x)].

%F The e.g.f. of this Appell sequence of polynomials P(n,x) is e^(xt) times the e.g.f. AC(t) of the aerated Catalan numbers A126120. AC(t) = I_1(2t)/t, where I_n(x) = T_n(d/dx) I_0(x) are the modified Bessel functions of the first kind and T_n, the Chebyshev polynomials of the first kind.

%F P(n,x) has the lowering and raising operators L = d/dx = D and R = d/dD log{M(x,D)} = x + d/dD log{AC(D)} = x + Sum_{n>=0} c(n) D^(2n+1)/(2n+1)! with c(n) = (-1)^n A180874(n+1), i.e., L P(n,x) = n P(n-1,x) and R P(n,x) = P(n+1,x).

%F (P(.,x) + y)^n = P(n,x+y) = Sum_{k=0..n} binomial(n,k) P(k,x) y^(n-k) = (b.+x+y)^n, where (b.)^k = b_k = A126120(k).

%F Exp(b.D) e^(xt) = exp[(x+b.)t] = exp[P(.,x)t] = e^(b.t) e^(xt) = e^(xt) AC(t).

%F See p. 12 of the Alexeev et al. link and A055151 for a refinement.

%F Shifted o.g.f: G(x,t) = [1-tx-sqrt[(1-tx)^2-4x^2]] / 2x = x + t x^2 + (1+t) x^3 + ... has the compositional inverse Ginv(x,t) = x / [1 + tx + x^2] = x - t x^2 +(-1+t^2) x^3 + (2t-t^3) x^4 + (1-3t^2+t^4) x^5 + ..., a shifted o.g.f. for the signed Chebyshev polynomials of the second kind of A049310 (cf. also the Fibonacci polynomials of A011973). Then the inversion formula of A134264, involving non-crossing partitions and free probability with their multitude of interpretations (cf. A125181 also), can be used with h_0 = 1, h_1 = t, and h_2 = 1 to interpret the coefficients of the Motzkin polynomials combinatorially.

%F (End)

%F From _Tom Copeland_, Jan 29 2016: (Start)

%F Provides coefficients of the inverse of f(x) = x / [1 + h1 x + h2 x^2], a bivariate generating function of A049310 (mod signs).

%F finv(x) = [(1-h1*x) - sqrt[(1-h1*x)^2-4h2*x^2]]/(2*h2*x) = x + h1 x^2 + (h2 + h1^2) x^3 + (3 h1 h2 + h1^3) x^4 + ... is a bivariate o.g.f. for this entry.

%F The infinitesimal generator for finv(x) is g(x) d/dx with g(x) = 1 /[df(x)/dx] = x^2 / [(f(x))^2 (1 - h2 x^2)] = (1 + h1 x + h2 x^2)^2 / (1 - h2 x^2) so that [g(x)d/dx]^n/n! x evaluated at x = 0 gives the row polynomials FI(n,h1,h2) of the compositional inverse of f(x), i.e., exp[x g(u)d/du] u |_(u=0) = finv(x) = 1 / [1 -x FI(.,h1,h2)]. Cf. A145271. E.g.,

%F FI(0,h1,h2) = 0

%F FI(1,h1,h2) = 1

%F FI(2,h1,h2) = 1 h1

%F FI(3,h1,h2) = 1 h2 + 1 h1^2

%F FI(4,h1,h2) = 3 h2 h1 + 1 h1^3

%F FI(5,h1,h2) = 2 h2^2 + 6 h2 h1^2 + 1 h1^4

%F FI(6,h1,h2) = 10 h2^2 h1 + 10 h2 h1^3 + 1 h1^5.

%F And with D = d/dh1, FI(n+1, h1,h2) = MT(n,h1,h2) = (b.y + h1)^n = Sum_{k=0..n} binomial(n,k) b(k) y^k h1^(n-k) = exp[(b.y D] (h1)^n = AC(y D) (h1)^n, where b(k) = A126120(k), y = sqrt(h2), and AC(t) is defined in my Jan 23 formulas above. Equivalently, AC(y D) e^(x h1) = exp[x MT(.,h1,h2)].

%F The MT polynomials comprise an Appell sequence in h1 with e.g.f. e^(h1*x) AC(xy) = exp[x MT(.,h1,h2)] with lowering operator L = d/dh1 = D, i.e., L MT(n,h1,h2) = dMT(n,h1,h2)/dh1 = n MT(n-1,h1,h2) and raising operator R = h1 + dlog{AC(y L)}/dL = h1 + Sum_{n>=0} c(n) h2^(n+1) D^(2n+1)/(2n+1)! = h1 + h2 d/dh1 - h2^2 (d/dh1)^3/3! + 5 h2^3 (d/dh1)^5/5! - ... with c(n) = (-1)^n A180874(n+1) (consistent with the raising operator in the Jan 23 formulas).

%F The compositional inverse finv(x) is also obtained from the non-crossing partitions of A134264 (or A125181) with h_0 = 1, h_1 = h1, h_2 = h2, and h_n = 0 for all other n.

%F See A238390 for the umbral compositional inverse in h1 of MT(n,h1,h2) and inverse matrix.

%F (End)

%F From _Tom Copeland_, Feb 13 2016: (Start)

%F z1(x,h1,h2) = finv(x), the bivariate o.g.f. above for this entry, is the zero that vanishes for x=0 for the quadratic polynomial Q(z;z1(x,h1,h2),z2(x,h1,h2)) = (z-z1)(z-z2) = z^2 - (z1+z2) z + (z1*z2) = z^2 - e1 z + e2 = z^2 - [(1-h1*x)/(h2*x)] z + 1/h2, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.

%F The other zero is given by z2(x,h1,h2) = (1 - h1*x)/(h2*x) - z1(x,h1,h2) = [1 - h1*x + sqrt[(1-h1*x)^2 - 4 h2*x^2]] / (2h2*x).

%F The two are the nontrivial zeros of the elliptic curve in Legendre normal form y^2 = z (z-z1)(z-z2), (see Landweber et al., p. 14, Ellingsrud, and A121448), and the zeros for the Riccati equation z' = (z - z1)(z - z2), associated to soliton solutions of the KdV equation (see Copeland link).

%F (End)

%F Comparing the shifted o.g.f. S(x) = x / (1 - h_1 x + h_2 x^2) for the bivariate Chebyshev polynomials S_n(h_1,h_2) of A049310 with the shifted o.g.f. H(x) = x / ((1 - a x)(1 - b x)) for the complete homogeneous symmetric polynomials H_n(a,b) = (a^(n+1)-b^(n+1)) / (a - b) shows that S_n(h_1,h_2) = H_n(a,b) for h_1 = a + b and h_2 = ab and, conversely, a = (h_1 + sqrt(h_1^2 - 4 h_2)) / 2 and b = (h_1 - sqrt(h_1^2 - 4 h_2)) / 2. The compositional inverse about the origin of S(x) gives a bivariate o.g.f. for signed Motzkin polynomials M_n(h_1,h_2) of this entry, and that of H(x) gives one for signed Narayana polynomials N_n(a,b) of A001263, thereby relating the bivariate Motzkin and Narayana polynomials by the indeterminate transformations. E.g., M_2(h_1,h_2) = h_2 + h_1^2 = ab + (a + b)^2 = a^2 + 3 ab + b^2 = N_2(a,b). - _Tom Copeland_, Jan 27 2024

%e Triangle begins:

%e 1;

%e 0, 1;

%e 1, 0, 1;

%e 0, 3, 0, 1;

%e 2, 0, 6, 0, 1;

%e 0, 10, 0, 10, 0, 1;

%e 5, 0, 30, 0, 15, 0, 1;

%e Row n has n+1 terms.

%e T(4,2)=6 because we have HHUD, HUDH, UDHH, HUHD, UHDH, UHHD, where U=(1,1), D=(1,-1) and H=(1,0).

%p G:=(1-t*z-sqrt(1-2*t*z+t^2*z^2-4*z^2))/2/z^2:

%p Gser:=simplify(series(G,z=0,16)): P[0]:=1:

%p for n from 1 to 13 do P[n]:=sort(coeff(Gser,z^n)) od:

%p seq(seq(coeff(t*P[n],t^k),k=1..n+1),n=0..13);

%p # Maple program for the triangular array:

%p T:=proc(n,k) if n-k mod 2 = 0 and k<=n then n!/k!/((n-k)/2)!/((n-k)/2+1)! else 0 fi end: TT:=(n,k)->T(n-1,k-1): matrix(10,10,TT);

%t T[n_,k_]:=If[n>=k&&EvenQ[n-k],n!/(k!((n-k)/2)!((n-k)/2+1)!),0];

%t Flatten[Table[T[n,k],{n,0,20},{k,0,n}]] (* _Peter J. C. Moses_, Apr 06 2013 *)

%t T[n_,k_] := If[OddQ[n - k], 0, Binomial[n, k] CatalanNumber[(n - k)/2]]; (* _Peter Luschny_, Jun 06 2018 *)

%Y Cf. A001006, A000108. A124027 is an essentially identical triangle.

%Y Cf. A011973, A049310, A055151, A060693, A180874, A121448, A125181, A126120, A134264, A145271, A238390.

%Y Cf. A001263.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Aug 30 2004