login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A132893 Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2). 2

%I

%S 1,2,4,1,9,4,21,13,1,50,40,6,121,118,27,1,296,340,106,8,730,965,381,

%T 46,1,1812,2708,1296,220,10,4521,7535,4241,935,70,1,11328,20828,13482,

%U 3676,395,12,28485,57266,41916,13658,1940,99,1

%N Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2).

%C Row n has 1 + floor(n/2) terms.

%C Row sums yield A005773.

%H Alois P. Heinz, <a href="/A132893/b132893.txt">Rows n = 0..200, flattened</a>

%H Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

%F T(n,0) = A091964(n).

%F Sum_{k=0..floor(n/2)} k*T(n,k) = A132894(n-1).

%F G.f.: G = G(t,z) satisfies z(1 - 3z + z^2 - tz^2)G^2 + (1 - 3z + z^2 - tz^2)G - 1 = 0 (see the Maple program for the explicit expression of G).

%e T(3,1)=4 because we have HUD, UDH, UDU and UUD.

%e Triangle starts:

%e 1;

%e 2;

%e 4, 1;

%e 9, 4;

%e 21, 13, 1;

%e 50, 40, 6;

%e 121, 118, 27, 1;

%p G:=((-1+3*z-z^2+t*z^2+sqrt((1+z+z^2-t*z^2)*(1-3*z+z^2-t*z^2)))*1/2)/(z*(1-3*z+z^2-t*z^2)): Gser:=simplify(series(G,z=0,15)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: for n from 0 to 12 do seq(coeff(P[n],t,j), j=0..floor((1/2)*n)) end do; # yields sequence in triangular form

%p # second Maple program:

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

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

%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_, Feb 01 2019

%t b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0, 0, If[x == 0, 1, b[x - 1, y, 1] + b[x - 1, y - 1, 1]*t + b[x - 1, y + 1, z]]]];

%t T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]] @ b[n, 0, 1];

%t T /@ Range[0, 15] // Flatten (* _Jean-François Alcover_, Oct 06 2019, after _Alois P. Heinz_ *)

%Y Cf. A005773, A091964, A132894.

%K nonn,tabf

%O 0,2

%A _Emeric Deutsch_, Oct 08 2007

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 19:15 EDT 2021. Contains 346359 sequences. (Running on oeis4.)