A109189 Triangle read by rows: T(n,k) is number of Grand Motzkin paths of length n having k (1,0)-steps at level zero. (A Grand Motzkin path is a path in the half-plane x>=0, starting at (0,0), ending at (n,0) and consisting of steps u=(1,1), d=(1,-1) and h=(1,0).).

1, 0, 1, 2, 0, 1, 2, 4, 0, 1, 8, 4, 6, 0, 1, 16, 20, 6, 8, 0, 1, 46, 40, 36, 8, 10, 0, 1, 114, 128, 72, 56, 10, 12, 0, 1, 310, 324, 254, 112, 80, 12, 14, 0, 1, 822, 932, 654, 432, 160, 108, 14, 16, 0, 1, 2238, 2540, 1986, 1128, 670, 216, 140, 16, 18, 0, 1, 6094, 7164, 5546

Offset

0,4

Comments

Row sums yield the central trinomial coefficients (A002426). T(n,0)=A109190(n). sum(k*T(n,k),k=0..n)=A015518(n).

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

G.f.= 1/(1-tz-2z^2*M), where M=1+zM+z^2*M^2=[1-z-sqrt(1-2z-3z^2)]/(2z^2) is the g.f. of the Motzkin numbers (A001006).

Example

T(4,1) = 4 because we have (h)uhd, (h)dhu, uhd(h) and dhu(h), where u=(1,1), d=(1,-1), h=(1,0) and the (1,0) steps at level 0 are shown between parentheses.
Triangle begins:
1;
0,1;
2,0,1;
2,4,0,1;
8,4,6,0,1;
16,20,6,8,0,1;

Maple

M:=(1-z-sqrt(1-2*z-3*z^2))/2/z^2: G:=1/(1-t*z-2*z^2*M): Gser:=simplify(series(G, z=0, 13)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 11 do seq(coeff(t*P[n], t^k), k=1..n+1) od;
# second Maple program:
b:= proc(x, y) option remember;
      `if`(abs(y)>x, 0, `if`(x=0, 1, expand(b(x-1, y)*
      `if`(y=0, t, 1) +b(x-1, y+1) +b(x-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, t, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);  # Alois P. Heinz, Feb 05 2014

Mathematica

nn=10; m=(1-x-(1-2x-3x^2)^(1/2))/(2x^2); CoefficientList[Series[1/(1-y x-2x^2m), {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Feb 05 2014 *)

Crossrefs

Cf. A002426, A109190, A015518, A001006.

Sequence in context: A115346 A140531 A117316 * A264157 A361853 A144172

Adjacent sequences: A109186 A109187 A109188 * A109190 A109191 A109192

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 21 2005

Status

approved