|
| |
|
|
A097610
|
|
Triangle read by rows: T(n,k) is number of Motzkin paths of length n and having k horizontal steps.
|
|
22
|
|
|
|
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).
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
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
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
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
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
|
|
|
REFERENCES
|
G. J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987, page 169.
|
|
|
LINKS
|
|
|
|
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) = C(n, k)*C((n-k)/2)*(1+(-1)^(n-k))/2 if k <= n, 0 otherwise. - Paul Barry, May 18 2005
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
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)
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)
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)
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
|
|
|
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];
T[n_, k_] := If[OddQ[n - k], 0, Binomial[n, k] CatalanNumber[(n - k)/2]]; (* Peter Luschny, Jun 06 2018 *)
|
|
|
CROSSREFS
|
Cf. A011973, A049310, A055151, A060693, A180874, A121448, A125181, A126120, A134264, A145271, A238390.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
