login
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).).
3
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
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 21 2005
STATUS
approved