A114711 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)).

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, 35, 144, 942, 1022, 175, 233, 1836, 2590, 700, 14, 377, 3522, 6260, 2450, 126, 610, 6666, 14570, 7770, 756, 987, 12473, 32870, 22890, 3570, 42, 1597, 23109, 72244

Offset: 1

Author

Emeric Deutsch, Dec 27 2005

Keywords

• nonn
• tabf

Comments

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.

Examples

			T(5,2)=3 because we have (UH)D(UU), (UHH)D(H) and (HUH)D(H) (the weak ascents are shown between parentheses).
Triangle begins:
   1;
   1;
   2;
   3,  1;
   5,  3;
   8,  9;
  13, 22,  2;
		

Links

• Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
• I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
• P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
• M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Crossrefs

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

Programs

Maple

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

Formula

Row n contains ceiling(n/3) terms.

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

Column 1 yields the Fibonacci numbers (A000045).

Column 2 yields A001628.

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

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

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