A126222 Triangle read by rows: T(n,k) is the number of 2-Motzkin paths (i.e., Motzkin paths with blue and red level steps) without red level steps on the x-axis, having length n and k level steps (0 <= k <= n).

1, 0, 1, 1, 0, 1, 0, 4, 0, 1, 2, 0, 11, 0, 1, 0, 15, 0, 26, 0, 1, 5, 0, 69, 0, 57, 0, 1, 0, 56, 0, 252, 0, 120, 0, 1, 14, 0, 364, 0, 804, 0, 247, 0, 1, 0, 210, 0, 1800, 0, 2349, 0, 502, 0, 1, 42, 0, 1770, 0, 7515, 0, 6455, 0, 1013, 0, 1, 0, 792, 0, 11055, 0, 27940, 0, 16962, 0

Offset: 0

Author

Emeric Deutsch, Dec 28 2006

Keywords

• nonn
• tabl

Comments

Row sums are the Catalan numbers (A000108).

A166073 appears to be a variant of A126222 where zeros are sorted to the start of each row. - R. J. Mathar, Aug 21 2010

Examples

			T(3,1)=4 because we have BUD, UBD, URD and UDB, where U=(1,1), D=(1,-1), B=blue (1,0), R=red (1,0).
Triangle starts:
1
0,1
1,0,1
0,4,0,1
2,0,11,0,1
0,15,0,26,0,1
5,0,69,0,57,0,1
0,56,0,252,0,120,0,1
14,0,364,0,804,0,247,0,1
0,210,0,1800,0,2349,0,502,0,1
42,0,1770,0,7515,0,6455,0,1013,0,1
0,792,0,11055,0,27940,0,16962,0,2036,0,1
132,0,8217,0,57035,0,95458,0,43086,0,4083,0,1
0,3003,0,62062,0,257257,0,305812,0,106587,0,8178,0,1
429,0,37037,0,381381,0,1049685,0,931385,0,258153,0,16369,0,1
0,11440,0,328328,0,2022384,0,3962140,0,2723280,0,614520,0,32752,0,1
1430,0,163592,0,2341976,0,9591764,0,14051660,0,7699800,0,1441928,0,65519,0,1
0,43758,0,1665456,0,14275716,0,41666184,0,47352820,0,21167312,0,3342489,0,131054,0,1
4862,0,712062,0,13527852,0,77161980,0,168567444,0,152915748,0,56818743,0,7667883,0,262125,0,1
...
		

Links

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

Crossrefs

Cf. A000108, A126223.

Programs

Maple

G:=(1-sqrt(1-4*z*t-4*z^2+4*z^2*t^2))/2/z/(t+z-t^2*z): Gser:=simplify(series(G,z=0,15)): for n from 0 to 12 do P[n]:=sort(expand(coeff(Gser,z,n))) od: for n from 0 to 12 do seq(coeff(P[n],t,j),j=0..n) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, expand(b(x-1, y)*`if`(y=0, 1, 2)*z+
       b(x-1, y+1) +b(x-1, y-1))))
    end:
T:= (n, k)-> coeff(b(n, 0), z, k):
seq(seq(T(n, k), k=0..n), n=0..15);  # Alois P. Heinz, May 20 2014

Mathematica

b[x_, y_] := b[x, y] = If[y>x || y<0, 0, If[x == 0, 1, Expand[b[x-1, y]*If[y == 0, 1, 2]*z + b[x-1, y+1] + b[x-1, y-1]]]]; T[n_, k_] := Coefficient[b[n, 0], z, k]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Formula

T(2n,0) = C(2n,n)/(n+1) (the Catalan numbers; A000108).

Sum_{k=0..n} k*T(n,k) = A126223(n).

G.f.: G = G(t,z) satisfies z(t + z - t^2*z)G^2 - G + 1 = 0.