اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدModular, $k$-noncrossing diagrams
159
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we compute the generating function of modular, $k$-noncrossing diagrams. A $k$-noncrossing diagram is called modular if it does not contains any isolated arcs and any arc has length at least four. Modular diagrams represent the deformation retracts of RNA pseudoknot structures cite{Stadler:99,Reidys:07pseu,Reidys:07lego} and their properties reflect basic features of these bio-molecules. The particular case of modular noncrossing diagrams has been extensively studied cite{Waterman:78b, Waterman:79,Waterman:93, Schuster:98}. Let ${sf Q}_k(n)$ denote the number of modular $k$-noncrossing diagrams over $n$ vertices. We derive exact enumeration results as well as the asymptotic formula ${sf Q}_k(n)sim c_k n^{-(k-1)^2-frac{k-1}{2}}gamma_{k}^{-n}$ for $k=3,..., 9$ and derive a new proof of the formula ${sf Q}_2(n)sim 1.4848, n^{-3/2},1.8489^{-n}$ cite{Schuster:98}.
قيم البحث
اقرأ أيضاً
In this paper we enumerate $k$-noncrossing tangled-diagrams. A tangled-diagram is a labeled graph whose vertices are $1,...,n$ have degree $le 2$, and are arranged in increasing order in a horizontal line. Its arcs are drawn in the upper halfplane wi
th a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of $k$-noncrossing tangled-diagrams $T_{k}(n) sim c_k n^{-((k-1)^2+(k-1)/2)} (4(k-1)^2+2(k-1)+1)^n$ for some $c_k>0$.
A set partition is said to be $(k,d)$-noncrossing if it avoids the pattern $12... k12... d$. We find an explicit formula for the ordinary generating function of the number of $(k,d)$-noncrossing partitions of ${1,2,...,n}$ when $d=1,2$.
In this paper we study $k$-noncrossing matchings. A $k$-noncrossing matching is a labeled graph with vertex set ${1,...,2n}$ arranged in increasing order in a horizontal line and vertex-degree 1. The $n$ arcs are drawn in the upper halfplane subject
to the condition that there exist no $k$ arcs that mutually intersect. We derive: (a) for arbitrary $k$, an asymptotic approximation of the exponential generating function of $k$-noncrossing matchings $F_k(z)$. (b) the asymptotic formula for the number of $k$-noncrossing matchings $f_{k}(n) sim c_k n^{-((k-1)^2+(k-1)/2)} (2(k-1))^{2n}$ for some $c_k>0$.
In this paper we present a selfcontained analysis and description of the novel {it ab initio} folding algorithm {sf cross}, which generates the minimum free energy (mfe), 3-noncrossing, $sigma$-canonical RNA structure. Here an RNA structure is 3-nonc
rossing if it does not contain more than three mutually crossing arcs and $sigma$-canonical, if each of its stacks has size greater or equal than $sigma$. Our notion of mfe-structure is based on a specific concept of pseudoknots and respective loop-based energy parameters. The algorithm decomposes into three parts: the first is the inductive construction of motifs and shadows, the second is the generation of the skeleta-trees rooted in irreducible shadows and the third is the saturation of skeleta via context dependent dynamic programming routines.
For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in ter
ms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haimans notion of a parking function symmetric function.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
