login
Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k valleys (n>=0, 0<=k<=floor(n/2)-1; a valley is a downstep followed by an upstep).
3

%I #18 Oct 23 2019 09:27:28

%S 1,1,2,4,8,1,17,4,37,13,1,82,40,5,185,116,21,1,423,326,80,6,978,899,

%T 279,31,1,2283,2444,924,140,7,5373,6578,2948,568,43,1,12735,17576,

%U 9136,2156,224,8,30372,46702,27690,7777,1035,57,1,72832,123568,82453,26952,4422

%N Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k valleys (n>=0, 0<=k<=floor(n/2)-1; a valley is a downstep followed by an upstep).

%C Also, triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k double rises (i.e. UU's, where U=(1,1)). E.g. T(5,1)=4 counts HUUDD, UUDDH, UUHDD and UUDHD, where U=(1,1), H=(1,0) and D=(1,-1).

%C Row sums are the Motzkin numbers (A001006). Column 0 gives A004148.

%H Alois P. Heinz, <a href="/A097885/b097885.txt">Rows n = 0..300, flattened</a>

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

%e Triangle starts:

%e 1;

%e 1;

%e 2;

%e 4;

%e 8, 1;

%e 17, 4;

%e 37, 13, 1;

%e ...

%e Row n (n>=2) has floor(n/2) terms.

%e T(5,1)=4 counts HU(DU)D, U(DU)DH, U(DU)HD and UH(DU)D (here U=(1,1), H=(1,0) and D=(1,-1); valleys are shown between parentheses).

%p eq:=G=1+z*G+z^2*G*(t*(G-1-z*G)+1+z*G): sol:=solve(eq,G): Gser:=simplify(series(sol[1],z=0,15)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(coeff(Gser,z^n)) od: 1,1,seq(seq(coeff(t*P[n],t^k),k=1..floor(n/2)),n=0..12);

%p # second Maple program:

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

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

%p expand(b(x-1, y+1, 1)*t)))

%p end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, 1)):

%p seq(T(n), n=0..15); # _Alois P. Heinz_, Oct 23 2019

%t (CoefficientList[#, t]& ) /@ CoefficientList[(-(t z^2) + Sqrt[((t-1) z^2 - z + 1)^2 + 4 z^2 (z t - z - t)] + z^2 + z - 1)/(2 z^2 (z t - z - t)) + O[z]^16, z] // Flatten (* _Jean-François Alcover_, Oct 23 2019 *)

%Y Cf. A001006, A004148, A097860.

%K nonn,tabf

%O 0,3

%A _Emeric Deutsch_, Sep 02 2004

%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, Jun 16 2007