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,12

Comments

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

Links

Table of n, a(n) for n=0..90.

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.]

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

Example

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.

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 k<n-1 then (k+1)*(a(n-k)-2*a(n-k-1)+a(n-k-2)) elif k=n-1 then 0 elif k=n then 1 else 0 fi end: seq(seq(T(n, k), k=0..n), n=0..12); # yields the sequence in linear form: a:=proc(n) if n=0 then 1 else sum(binomial(k, n-k)*binomial(k, n-k+1)/k, k=ceil((n+1)/2)..n) fi end: T:=proc(n, k) if k<0 then 0 elif k<n-1 then (k+1)*(a(n-k)-2*a(n-k-1)+a(n-k-2)) elif k=n-1 then 0 elif k=n then 1 else 0 fi end: TT:=(n, k)->T(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 *)

Crossrefs

Cf. A004148, A097779.

Sequence in context: A089615 A301593 A089731 * A123679 A167948 A111755

Adjacent sequences: A097095 A097096 A097097 * A097099 A097100 A097101

Keyword

nonn,tabl

Author

Emeric Deutsch, Sep 15 2004

Status

approved