A089738 Triangle of T(n,k)=number of peakless Motzkin paths of length n containing k valleys (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 16, 1, 33, 4, 69, 13, 146, 38, 1, 312, 106, 5, 673, 284, 21, 1463, 742, 77, 1, 3202, 1904, 261, 6, 7050, 4823, 831, 31, 15605, 12096, 2534, 136, 1, 34705, 30106, 7474, 540, 7, 77511, 74484, 21480, 1984, 43

Offset

0,4

Comments

Rows 0,1,2 contain one entry each and row n (n>=3) contains floor(n/3) entries.

References

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

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. G(t, z) satisfies G=1+zG+z^2*(G-1)[G-(1-t)(G-1-zG)].

Example

T(7,1)=4 because we have HUH(DU)HD, UH(DU)HDH, UH(DU)HHD and UHH(DU)HD, where U=(1,1), D=(1,-1) and H=(1,0); the valleys are shown between parentheses.

Crossrefs

Row sums give A004148.

Sequence in context: A317506 A317501 A097777 * A110333 A247292 A069783

Adjacent sequences: A089735 A089736 A089737 * A089739 A089740 A089741

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 07 2004

Status

approved