login
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/3)).
0

%I #23 Mar 25 2024 06:46:13

%S 1,1,2,3,1,5,3,8,9,13,22,2,21,51,10,34,111,40,55,233,130,5,89,474,380,

%T 35,144,942,1022,175,233,1836,2590,700,14,377,3522,6260,2450,126,610,

%U 6666,14570,7770,756,987,12473,32870,22890,3570,42,1597,23109,72244

%N Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/3)).

%C A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps.

%H Jean-Luc Baril and José Luis Ramírez, <a href="https://arxiv.org/abs/2302.12741">Descent distribution on Catalan words avoiding ordered pairs of Relations</a>, arXiv:2302.12741 [math.CO], 2023.

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1978), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="https://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

%F Row n contains ceiling(n/3) terms.

%F Row sums yield the RNA secondary structure numbers (A004148).

%F Column 1 yields the Fibonacci numbers (A000045).

%F Column 2 yields A001628.

%F T(3n+1,n+1) = A000108(n) (the Catalan numbers).

%F Sum_{k=1..ceiling(n/3)} k*T(n,k) = A051286(n-1) (n >= 1).

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

%e T(5,2)=3 because we have (UH)D(UU), (UHH)D(H) and (HUH)D(H) (the weak ascents are shown between parentheses).

%e Triangle begins:

%e 1;

%e 1;

%e 2;

%e 3, 1;

%e 5, 3;

%e 8, 9;

%e 13, 22, 2;

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

%Y Cf. A004148, A000045, A001628, A000108, A051286.

%K nonn,tabf

%O 1,3

%A _Emeric Deutsch_, Dec 27 2005