|
%I #27 Oct 24 2017 09:31:11
%S 1,1,0,1,0,1,1,0,1,2,1,0,2,2,4,1,0,4,4,4,8,1,0,9,8,8,8,17,1,0,21,18,
%T 16,16,17,38,1,0,51,42,36,32,34,38,89,1,0,127,102,84,72,68,76,89,216,
%U 1,0,323,254,204,168,153,152,178,216,539,1,0,835,646,508,408,357,342,356,432,539,1374
%N Triangle read by rows: T(n,k) = number of Motzkin paths of length n and having abscissa of first return (i.e., first down step hitting the x-axis) equal to k (k>0); T(n,0)=1 (accounts for the paths consisting only of level steps).
%C Row sums are the Motzkin numbers (A001006).
%H G. C. Greubel, <a href="/A097854/b097854.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%F G.f.: (1-t*z+t^2*z^2*M(t*z)*M(z) - t^2*z^3*M(t*z)*M(z))/(1-z-t*z+t*z^2), where M(z)=(1-z-sqrt(1-2*z-3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers.
%F T(n,k) = m(n-k)*Sum_{j=0..k-2} m(j), where m(n) = A001006(n) are the Motzkin numbers.
%e Triangle starts:
%e 1;
%e 1, 0;
%e 1, 0, 1;
%e 1, 0, 1, 2;
%e 1, 0, 2, 2, 4;
%e 1, 0, 4, 4, 4, 8;
%e Row n has n+1 terms.
%e T(5,3)=4 because the Motzkin paths of length 5 and having abscissa of first return equal to 3 are HU(D)HH, HU(D)UD, UH(D)HH and UH(D)UD (first returns to axis shown between parentheses); here U=(1,1), H=(1,0) and D=(1,-1).
%p G:=(1-t*z+t^2*z^2*M(t*z)*M(z)-t^2*z^3*M(t*z)*M(z))/(1-z-t*z+t*z^2): M:=z->(1-z-sqrt(1-2*z-3*z^2))/2/z^2: Gser:=simplify(series(G,z=0,14)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser,z^n) od: seq(seq(coeff(t*P[n],t^k),k=1..n+1),n=0..12); M:=(1-z-sqrt(1-2*z-3*z^2))/2/z^2: Mser:=series(M,z=0,15): m[0]:=1: for n from 1 to 12 do m[n]:=coeff(Mser,z^n) od: T:=proc(n,k) if k=0 then 1 elif k<=n then m[n-k]*sum(m[j],j=0..k-2) else 0 fi end: TT:=(n,k)->T(n-1,k-1): matrix(11,11,TT); # generates the triangle:
%t (* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, 0] = 1; t[n_, k_] := m[n - k]*Sum[m[j], {j, 0, k - 2}]; Table[t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 10 2013 *)
%Y Cf. A001006.
%K nonn,tabl
%O 0,10
%A _Emeric Deutsch_, Aug 31 2004
%E Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013
%E Terms a(75) and beyond from _G. C. Greubel_, Oct 23 2017
|
