

A097610


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


21



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, 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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,8


COMMENTS

Row sums are the Motzkin numbers (A001006). Column 0 gives the aerated Catalan numbers (A000108).
Applied as a matrix to the power series r^n, it gives the sequence which counts rcolored Motzkin paths of length n; equivalently, sum{k=0..n,C(n,k)C((nk)/2)(1+(1)^(nk)r^k/2} = sum{k=0..floor(k/2), C(n,2k)C(k)r^(n2k)}.  Paul Barry, May 18 2005
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_(n1)(x)+Sum_{j, 0<=j<=(n2)}P_j(x)*P_(n2j)(x); essentially the same as A124027.  Philippe Deléham, Oct 03 2007
G. J. Chaitin's numbers of sexpressions 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
Exponential Riordan array [Bessel_I(1,2x)/x,x].  Paul Barry, Mar 24 2010
Diagonal sums are the aerated large Schroeder numbers.  Paul Barry, Apr 21 2010
Nonvanishing antidiagonals are rows of A060693.  Tom Copeland, Feb 03 2016
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 / [12tx+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) = [(1h1*y)  sqrt[(1h1*y)^24h2*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


REFERENCES

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


LINKS

Peter J. C. Moses, Table of n, a(n) for n = 0..1080
N. Alexeev, J. Andersen, R. Penner, P. Zograf, Enumeration of chord diagrams on many intervals and their nonorientable analogs, arXiv:1307.0967 [math.CO], 20132014.
Tom Copeland, The Elliptic Lie Triad: Riccati and KdV Equations, Infinigens, and Elliptic Genera
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
G. Ellingsrud, Elliptic curvesBasics, course notes
P. Landweber, D. Ravenel, R. Stong, Periodic cohomology theories defined by elliptic curves
Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227238.  From N. J. A. Sloane, Oct 13 2012


FORMULA

G.f.: [1tzsqrt(12tz+t^2*z^24z^2)]/(2z^2).
T(n, k) = n!/[k!((nk)/2)!((nk)/21)! ] = A055151(n, (nk)/2) if nk is a nonnegative even number; otherwise T(n, k) = 0.
T(n, k) = if(k<=n, C(n, k)C((nk)/2)(1+(1)^(nk))/2, 0)  Paul Barry, May 18 2005
T(n,k) = A121448(n,k)/2^k.  Philippe Deléham, Aug 17 2006
Sum_[k,0<=k<=n}T(n,k)*2^k = A000108(n+1).  Philippe Deléham, Aug 22 2006
Sum_{k, 0<=k<=n}T(n,k)*3^k = A002212(n+1).  Philippe Deléham, Oct 03 2007
G.f.: 1/(1x*yx^2/(1x*yx^2/(1x*yx^2/..... (continued fraction);  Paul Barry, Dec 15 2008
Sum_{k, 0<=k<=n}T(n,k)*4^k = A005572(n).  Philippe Deléham, Dec 03 2009
T(n,k) = A007318(n,k)*A126120(nk).  Philippe Deléham, Dec 12 2009
From Tom Copeland, Jan 23 2016: (Start)
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)].
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.
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(n1,x) and R P(n,x) = P(n+1,x).
(P(.,x) + y)^n = P(n,x+y) = Sum_{k=0..n} binomial(n,k) P(k,x) y^(nk) = (b.+x+y)^n, where (b.)^k = b_k = A126120(k).
Exp(b.D) e^(xt) = exp[(x+b.)t] = exp[P(.,x)t] = e^(b.t) e^(xt) = e^(xt) AC(t).
See p. 12 of the Alexeev et al. link and A055151 for a refinement.
Shifted O.g.f: G(x,t) = [1txsqrt[(1tx)^24x^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 + (2tt^3) x^4 + (13t^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 noncrossing 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.
(End)
From Tom Copeland, Jan 29 2016: (Start)
Provides coefficients of the inverse of f(x) = x / [1 + h1 x + h2 x^2], a bivariate generating function of A049310 (mod signs).
finv(x) = [(1h1*x)  sqrt[(1h1*x)^24h2*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.
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.,
FI(0,h1,h2) = 0
FI(1,h1,h2) = 1
FI(2,h1,h2) = 1 h1
FI(3,h1,h2) = 1 h2 + 1 h1^2
FI(4,h1,h2) = 3 h2 h1 + 1 h1^3
FI(5,h1,h2) = 2 h2^2 + 6 h2 h1^2 + 1 h1^4
FI(6,h1,h2) = 10 h2^2 h1 + 10 h2 h1^3 + 1 h1^5.
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^(nk) = 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)].
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(n1,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).
The compositional inverse finv(x) is also obtained from the noncrossing partitions of A134264 (or A125181) with h_0 = 1, h_1 = h1, h_2 = h2, and h_n = 0 for all other n.
See A238390 for the umbral compositional inverse in h1 of MT(n,h1,h2) and inverse matrix.
(End)
From Tom Copeland, Feb 13 2016: (Start)
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)) = (zz1)(zz2) = z^2  (z1+z2) z + (z1*z2) = z^2  e1 z + e2 = z^2  [(1h1*x)/(h2*x)] z + 1/h2, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.
The other zero is given by z2(x,h1,h2) = (1  h1*x)/(h2*x)  z1(x,h1,h2) = [1  h1*x + sqrt[(1h1*x)^2  4 h2*x^2]] / (2h2*x).
The two are the nontrivial zeros of the elliptic curve in Legendre normal form y^2 = z (zz1)(zz2), (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).
(End)


EXAMPLE

Triangle begins:
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;
Row n has n+1 terms.
T(4,2)=6 because we have HHUD, HUDH, UDHH, HUHD, UHDH, UHHD, where U=(1,1),
D=(1,1) and H=(1,0).


MAPLE

G:=(1t*zsqrt(12*t*z+t^2*z^24*z^2))/2/z^2:
Gser:=simplify(series(G, z=0, 16)): P[0]:=1:
for n from 1 to 13 do P[n]:=sort(coeff(Gser, z^n)) od:
seq(seq(coeff(t*P[n], t^k), k=1..n+1), n=0..13);
# Maple program for the triangular array:
T:=proc(n, k) if nk mod 2 = 0 and k<=n then n!/k!/((nk)/2)!/((nk)/2+1)! else 0 fi end: TT:=(n, k)>T(n1, k1): matrix(10, 10, TT);


MATHEMATICA

T[n_, k_]:=If[n>=k&&EvenQ[nk], n!/(k!((nk)/2)!((nk)/2+1)!), 0];
Flatten[Table[T[n, k], {n, 0, 20}, {k, 0, n}]] (* Peter J. C. Moses, Apr 06 2013 *)


CROSSREFS

Cf. A001006, A000108. A124027 is an essentially identical triangle.
Cf. A011973, A049310, A055151, A060693, A180874, A121448, A125181, A126120, A134264, A145271, A238390.
Sequence in context: A021336 A100749 A124027 * A161556 A242869 A224878
Adjacent sequences: A097607 A097608 A097609 * A097611 A097612 A097613


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Aug 30 2004


STATUS

approved



