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

 

Logo


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
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 r-colored Motzkin paths of length n; equivalently, sum{k=0..n,C(n,k)C((n-k)/2)(1+(-1)^(n-k)r^k/2} = sum{k=0..floor(k/2), C(n,2k)C(k)r^(n-2k)}. - 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_(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

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

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

Non-vanishing 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 / [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

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 non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014.

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 curves--Basics, 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), 227-238. - From N. J. A. Sloane, Oct 13 2012

FORMULA

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

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.

T(n, k) = if(k<=n, C(n, k)C((n-k)/2)(1+(-1)^(n-k))/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/(1-x*y-x^2/(1-x*y-x^2/(1-x*y-x^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(n-k). - 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(n-1,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^(n-k) = (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) = [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.

(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) = [(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.

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^(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)].

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).

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.

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)) = (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.

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).

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).

(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:=(1-t*z-sqrt(1-2*t*z+t^2*z^2-4*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 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);

MATHEMATICA

T[n_, k_]:=If[n>=k&&EvenQ[n-k], n!/(k!((n-k)/2)!((n-k)/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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 14:41 EST 2018. Contains 299623 sequences. (Running on oeis4.)