Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Modular, k-noncrossing diagrams. | Modular k-noncrossing diagrams Christian M. Reidysa Rita R. Wangb and Albus Y. Y. Zhaoc Center for Combinatorics LPMC-TJKLC Nankai University Tianjin 300071 . China a duck@ b wangrui@ c zyy@ Submitted Mar 27 2010 Accepted May 16 2010 Published May 20 2010 Abstract In this paper we compute the generating function of modular k-noncrossing diagrams. A k-noncrossing diagram is called modular if it does not contain any isolated arcs and any arc has length at least four. Modular diagrams represent the deformation retracts of RNA tertiary structures and their properties reflect basic features of these bio-molecules. The particular case of modular noncrossing diagrams has been extensively studied. Let Qk n denote the number of modular k-noncrossing diagrams over n vertices. We derive exact enumeration results as well as the asymptotic formula Qk n ckn- k-1 - 2 Y-n for k 3 . 9 and derive a new proof of the formula Q2 n n-3 2 Hofacker et al. 1998 . 1 Introduction A ribonucleic acid RNA molecule is the helical configuration of a primary structure of nucleotides A G U and C together with Watson-Crick A-U G-C and U-G base pairs. It is well-known that RNA structures exhibit cross-serial nucleotide interactions called pseudoknots. First recognized in the turnip yellow mosaic virus in 17 they are now known to be widely conserved in functional RNA molecules. Modular k-noncrossing diagrams represent a model of RNA pseudoknot structures 5 9 11 that is RNA structures exhibiting cross-serial base pairings. The particular case of modular noncrossing diagrams . RNA secondary structures has been extensively studied 7 14 21 22 . The main result of this paper is the computation of the generating function of modular k-noncrossing diagrams Qk z . A diagram is a labeled graph over the vertex set n 1 . n with vertex degrees not greater than one. The standard representation of a THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R76
