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

%I #16 Jul 22 2017 09:05:19

%S 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,

%T 252,0,120,0,1,14,0,364,0,804,0,247,0,1,0,210,0,1800,0,2349,0,502,0,1,

%U 42,0,1770,0,7515,0,6455,0,1013,0,1,0,792,0,11055,0,27940,0,16962,0

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

%C Row sums are the Catalan numbers (A000108).

%C A166073 appears to be a variant of A126222 where zeros are sorted to the start of each row. - _R. J. Mathar_, Aug 21 2010

%H Alois P. Heinz, <a href="/A126222/b126222.txt">Rows n = 0..140, flattened</a>

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

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

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

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

%e Triangle starts:

%e 1

%e 0,1

%e 1,0,1

%e 0,4,0,1

%e 2,0,11,0,1

%e 0,15,0,26,0,1

%e 5,0,69,0,57,0,1

%e 0,56,0,252,0,120,0,1

%e 14,0,364,0,804,0,247,0,1

%e 0,210,0,1800,0,2349,0,502,0,1

%e 42,0,1770,0,7515,0,6455,0,1013,0,1

%e 0,792,0,11055,0,27940,0,16962,0,2036,0,1

%e 132,0,8217,0,57035,0,95458,0,43086,0,4083,0,1

%e 0,3003,0,62062,0,257257,0,305812,0,106587,0,8178,0,1

%e 429,0,37037,0,381381,0,1049685,0,931385,0,258153,0,16369,0,1

%e 0,11440,0,328328,0,2022384,0,3962140,0,2723280,0,614520,0,32752,0,1

%e 1430,0,163592,0,2341976,0,9591764,0,14051660,0,7699800,0,1441928,0,65519,0,1

%e 0,43758,0,1665456,0,14275716,0,41666184,0,47352820,0,21167312,0,3342489,0,131054,0,1

%e 4862,0,712062,0,13527852,0,77161980,0,168567444,0,152915748,0,56818743,0,7667883,0,262125,0,1

%e ...

%p 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

%p # second Maple program:

%p b:= proc(x, y) option remember; `if`(y>x or y<0, 0,

%p `if`(x=0, 1, expand(b(x-1, y)*`if`(y=0, 1, 2)*z+

%p b(x-1, y+1) +b(x-1, y-1))))

%p end:

%p T:= (n, k)-> coeff(b(n, 0), z, k):

%p seq(seq(T(n, k), k=0..n), n=0..15); # _Alois P. Heinz_, May 20 2014

%t 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_ *)

%Y Cf. A000108, A126223.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Dec 28 2006