login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097610 Triangle read by rows: T(n,k) is number of Motzkin paths of length n and having k horizontal steps. 21

%I

%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<=k<=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<=j<=(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[p(j, x)*p(k - j, x), {j, 2, k - 1}]. 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, 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 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, 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, 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) = if(k<=n, C(n, k)C((n-k)/2)(1+(-1)^(n-k))/2, 0). - _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)

%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),

%e 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.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Aug 30 2004

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 9 19:51 EST 2019. Contains 329879 sequences. (Running on oeis4.)