Enumerative aspects of secondary structures
- 作者：Do&scaron ; lic ; Tomislav ; Svrtan ; Dragutin ; Veljan ; Darko
- 关键词：05A15 ; 05A16 ; 05A20 ; 05B50 ; 05C30 ; 05C70 ; 33C45 ; 92D20 ; Secondary structures ; Motzkin path ; Motzkin numbers ; Dyck path ; Narayana numbers ; Log-convexity ; Orthogonal polynomials
- 刊名：Discrete Mathematics
- 出版年：2004
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：August 6, 2004
- 卷：285
- 期：1-3
- 页码：67-82
- 文件大小：288 K
摘要
A secondary structure is a planar, labeled graph on the vertex set {1,…,n} having two kind of edges: the segments [i,i+1], for 1≤i≤n−1 and arcs in the upper half-plane connecting some vertices i,j, i≤j, where j−i>l, for some fixed integer l. Any two arcs must be totally disjoint. We enumerate secondary structures with respect to their size n, rank l and order k (number of arcs), obtaining recursions and, in some cases, explicit formulae in terms of Motzkin, Catalan, and Narayana numbers. We give the asymptotics for the enumerating sequences and prove their log-convexity, log-concavity and unimodality. It is shown how these structures are connected with hypergeometric functions and orthogonal polynomials.