A097098 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n and having a total of k level steps (1,0) to the left of the first (1,1) step and to the right of the last (1,-1) step (i.e., total length of the two tails is k; can be easily expressed in terms of RNA secondary structure terminology).

1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 2, 2, 3, 0, 0, 1, 5, 4, 3, 4, 0, 0, 1, 11, 10, 6, 4, 5, 0, 0, 1, 25, 22, 15, 8, 5, 6, 0, 0, 1, 58, 50, 33, 20, 10, 6, 7, 0, 0, 1, 135, 116, 75, 44, 25, 12, 7, 8, 0, 0, 1, 317, 270, 174, 100, 55, 30, 14, 8, 9, 0, 0, 1, 750, 634, 405, 232, 125, 66, 35, 16, 9, 10, 0, 0, 1

Offset: 0

Author

Emeric Deutsch, Sep 15 2004

Keywords

• nonn
• tabl

Comments

Row sums yield the RNA secondary structure numbers (A004148). Column 0 is A097779.

Examples

			Triangle starts:
  1;
  0, 1;
  0, 0, 1;
  1, 0, 0, 1;
  1, 2, 0, 0, 1;
  2, 2, 3, 0, 0, 1;
  5, 4, 3, 4, 0, 0, 1;
Row n has n+1 terms.
T(6,3)=4 because we have (HHH)UHD, (HH)UHD(H), (H)UHD(HH) and UHD(HHH), where U=(1,1), H=(1,0) and D=(1,-1); the 3 required level steps are shown between parentheses.
		

Links

• 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 (1979), 261-272.
• M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Crossrefs

Cf. A004148, A097779.

Programs

Maple

a:=proc(n) if n=0 then 1 else sum(binomial(j,n-j)*binomial(j,n-j+1)/j,j=ceil((n+1)/2)..n) fi end: T:=proc(n,k) if k<0 then 0 elif kT(n-1,k-1): matrix(13,13,TT); # yields the sequence in matrix form:

Mathematica

(* c is A004148 *)
c[n_] := c[n] = If[n == 0, 1, c[n-1] + Sum[c[k]*c[n-2-k], {k, n-2}]];
T[n_, k_] := T[n, k] = Which[k < 0, 0, k < n-1, (k+1)*(c[n-k] - 2*c[n-k-1] + c[n-k-2]), k == n-1, 0, k == n, 1, True, 0];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 30 2024 *)

Formula

T(n,k) = (k+1)T(n-k, 0) for k < n; T(n,n) = 1. T(n,0) = a(n)-2a(n-1) + a(n-2) (n >= 2), where a(n) = Sum_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k, n-k+1)/k = A004148(n).

G.f.: 1/(1-tz) + (1-z)(g-1-zg)/(1-tz)^2, where g = (1 - z + z^2 - sqrt(1 - 2z - z^2 - 2z^3 + z^4))/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).