A089741 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k UHH...HD's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 1, 1, 1, 3, 1, 7, 1, 15, 1, 1, 31, 5, 1, 63, 18, 1, 127, 56, 1, 1, 255, 160, 7, 1, 511, 432, 34, 1, 1023, 1120, 138, 1, 1, 2047, 2816, 500, 9, 1, 4095, 6912, 1672, 55, 1, 8191, 16640, 5264, 275, 1, 1, 16383, 39424, 15808, 1205, 11, 1, 32767, 92160, 45696, 4797

Offset

0,7

References

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, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Links

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

M. S. Waterman, Home Page (contains copies of his papers)

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.

Formula

G.f.=[1-2z+2z^2-tz^3-sqrt[(1-tz^3)*(1-4z+4z^2-tz^3)]]/[2z^2*(1-z].

Example

T(7,2)=5 because we have H(UHD)(UHD), (UHD)H(UHD), (UHD)(UHD)H, (UHD)(UHHD) and (UHHD)(UHD) (the required subwords are shown between parentheses).
1; 1; 1; 1,1; 1,3; 1,7; 1,15,1; 1,31,5; 1,63,18; 1,127,56,1; 1,255,160,7;

Crossrefs

Row sums yield A004148. Column 1 is A000225, column 2 is A001793.

Sequence in context: A160627 A114712 A321452 * A089736 A205479 A094024

Adjacent sequences: A089738 A089739 A089740 * A089742 A089743 A089744

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 08 2004

Status

approved