Shapes of RNA Pseudoknot Structures

Theorem 1

(Flajolet and Sedgewick, 2009) (a) Suppose f (z) = (1 − z)^−α, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \alpha \in {\mathbb C} \setminus {\mathbb Z}_{ \le 0} $$ \end{document} then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} [ z^n ] \, f ( z ) \ \sim \ \frac { n^ { \alpha - 1 } } { \Gamma ( \alpha ) } & \left[ 1 + \frac { \alpha ( \alpha - 1 ) } { 2n } + \frac { \alpha ( \alpha - 1 ) ( \alpha - 2 ) ( 3 \alpha - 1 ) } { 24 n^2 } + \right. \\ & \quad \left. \frac { \alpha^2 ( \alpha - 1 ) ^2 ( \alpha - 2 ) ( \alpha - 3 ) } { 48n^3 } + O \left( \frac { 1 } { n^4 } \right) \right] . \tag { 9 } \end{align*} \end{document}

(b) Suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ f ( z ) = ( 1 - z ) ^ { r } \log \left( \frac { 1 } { 1 - z } \right) $$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ r \in {\mathbb Z}_{ \geq 0} $$ \end{document} , then we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} [ z^n ] \,f ( z ) \,\sim\, ( - 1 ) ^r \frac { r! } { n ( n - 1 ) \ldots ( n - r ) } . \tag { 10 } \end{align*} \end{document}

Theorem 2

(Flajolet and Sedgewick, 2009) Let f (z) be a D-finite function having a unique dominant singularity z = 1. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} g ( z ) = ( 1 - z ) ^ { \alpha } \log^ { \beta } \left( \frac { 1 } { 1 - z } \right) , \quad \alpha , \beta \in { \mathbb R } . \end{align*} \end{document}

That is, we have in the intersection of a neighborhood of 1 \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} f ( z ) = \Theta ( g ( z ) ) \quad for\ z \rightarrow 1. \tag{11} \end{align*} \end{document}

Then we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} [ z^n ] f ( z ) = \Theta \left( [ z^n ] g ( z ) \right) . \tag{12} \end{align*} \end{document}

Theorems 1 and 2 facilitate to derive the asymptotics of the coefficients of the D-finite function F _k (z) at its unique dominant singularity. More precisely, we shall encounter a particular instance of the supercritical paradigm, where we have the following situation: we are given a D-finite function, f (z) and an algebraic function g(u) satisfying g(0) = 0. Furthermore, we suppose that f (g(u)) has a unique real valued dominant singularity γ and g is regular in a disc with radius slightly larger than γ. Then the supercritical paradigm stipulates that the subexponential factors of f (g(u)) at u = 0, given that g(u) satisfies certain conditions, coincide with those of f (z).

Proposition 1

Let ψ(z) be an algebraic, analytic function in a domain \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal D} = \{ z \mid \mid z \mid \leq r \} $$ \end{document} such that ψ(0) = 0. In addition, suppose γ is the unique dominant singularity of F _k (ψ(z)) and minimum positive real solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \psi ( \gamma ) = \rho_k^2 , \mid \gamma \mid < r $$ \end{document} , ψ′(γ) ≠ 0. Then F _k (ψ(z)) has a singular expansion and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} [ z^n ] { \bf F } _k ( \psi ( z ) ) \,\sim\, A n^ { - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \frac { 1 } { \gamma } \right) ^n , \tag { 13 } \end{align*} \end{document}

where A is some constant.

In the following, we will compute the generating functions via the symbolic enumeration method (Flajolet and Sedgewick, 2009). For this purpose, we need the notion of a combinatorial class. A combinatorial class ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} , w_{ \cal C} $$ \end{document} ) is a set together with a size-function, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ w_{ \cal C}: { \cal C} \longrightarrow {\mathbb Z}^ + $$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C}_n = w_{ \cal C}^{ - 1} ( n ) $$ \end{document} is finite for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ n \in {\mathbb Z}^ + $$ \end{document} . We write w instead of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ w_{ \cal C} $$ \end{document} and set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ C_n = \mid { \cal C}_n \mid $$ \end{document} . Two special combinatorial classes are \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\cal E} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\cal Z} $$ \end{document} which contain only one element of size 0 and 1, respectively. The generating function of a combinatorial class \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} $$ \end{document} is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf C} ( z ) = \sum_{c \in{ \cal C}}z^{w ( c ) } = \sum_{n \geq 0}C_n z^n , \tag{14} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C}_n \subset { \cal C} $$ \end{document} . In particular, the generating functions of the classes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal E} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal Z} $$ \end{document} are E(z) = 1 and Z(z) = z. Suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} , { \cal D} $$ \end{document} are combinatorial classes. Then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} { \cal C} \end{document} is isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} \cong{ \cal D} $$ \end{document} , if and only if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \forall n \geq 0 , \mid { \cal C}_n \mid = \mid { \cal D}_n \mid $$ \end{document} . In the following, we shall identify isomorphic combinatorial classes and write \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} = { \cal D} $$ \end{document} if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} \cong{ \cal D} $$ \end{document} . We set

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} + { \cal D} : = \,{ \cal C} \cup { \cal D} $$ \end{document} , if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} \cap { \cal D} = \O $$ \end{document} and for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \alpha \in { \cal C} + { \cal D} $$ \end{document} ,

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} w_{{ \cal C} + { \cal D}} ( \alpha ) = \begin{cases}w_{ \cal C} ( \alpha ) \quad { \rm if} \ \alpha \in{ \cal C} \\ w_{ \cal D} ( \alpha ) \quad { \rm if} \ \alpha \in{ \cal D}.\end{cases} \tag{15} \end{align*} \end{document}

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C} \times{ \cal D} :\,=\,\{ \alpha = ( c , d ) \mid c \in{ \cal C} , d \in { \cal D} \} $$ \end{document} and for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \alpha \in { \cal C} \times { \cal D} $$ \end{document} ,

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} w_{{ \cal C} \times { \cal D}} ( ( c , d ) ) = w_{ \cal C} ( c ) + w_{ \cal D} ( d ) . \tag{16} \end{align*} \end{document}

and furthermore \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal C}^m :=\,\prod\nolimits_{h = 1}^m { \cal C} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm SEQ} ( { \cal C} ) :=\,{ \cal E} + { \cal C} + { \cal C}^2 + \cdots $$ \end{document} . Plainly, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm SEQ} ( { \cal C} ) $$ \end{document} is a combinatorial class if and only if there is no element in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \cal C}$$ \end{document} of size 0. We immediately observe:

Proposition 2

Suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal A} , { \cal C} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal D} $$ \end{document} are combinatorial classes with generating functions A(z), C(z) and D(z). Then

(a)  \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal A} = { \cal C} + { \cal D} \,\Longrightarrow { \bf A} ( z ) = { \bf C} ( z ) + { \bf D} ( z ) $$ \end{document}

(b)  \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal A} = { \cal C} \times { \cal D} \,\Longrightarrow { \bf A} ( z ) = { \bf C} ( z ) \cdot { \bf D} ( z ) $$ \end{document}

(c)  \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal A } = { \rm SEQ } ( { \cal C } ) \,\Longrightarrow { \bf A } ( z ) = \frac { 1 } { 1 - { \bf C } ( z ) } . $$ \end{document}

3. Combinatorics Of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_{ \rm k}^{ \bf 5} $$\end{document} -Shapes

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \cal G}_k ( s , m )$$ \end{document} denote the set of the k-noncrossing matchings of length 2s with m 1-arcs. In our first lemma, we will compute the bivariate generating function of g_k(s, m), i.e. the number of k-noncrossing matchings of length 2s with exactly m 1-arcs.

Lemma 1

Suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ k , s , m \in {\mathbb N} $$ \end{document} , k ≥ 2, 0 ≤ m ≤ s. Then g_k(s, m) satisfies the recursion \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} ( m + 1 ) g_k ( s + 1 , m + 1 ) = ( m + 1 ) g_k ( s , m + 1 ) + ( 2s + 1 - m ) g_k ( s , m ). \tag{17} \end{align*} \end{document}

Furthermore, the generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf G}_k ( x , y ) = \sum\nolimits_{s \geq 0} \sum\nolimits_{m = 0}^{s}g_k ( s , m ) x^sy^m $$ \end{document} is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _k ( x , y ) = \frac { 1 } { x + 1 - yx } { \bf F } _k \left( \frac { x } { ( x + 1 - yx ) ^2 } \right) . \tag { 18 } \end{align*} \end{document}

Proof

Choose a k-noncrossing matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \delta \in { \cal G}_k ( s + 1 , m + 1 ) $$ \end{document} and label one 1-arc. We have (m + 1)g_k(s + 1, m + 1) different such labeled k-noncrossing matchings. On the other hand, in order to obtain such a labeled matching, we can also insert one labeled 1-arc in a k-noncrossing matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \delta^{ \prime} \in { \cal G}_k ( s , m + 1 ) $$ \end{document} . In this case, we can only put it inside one original 1-arc in δ′ in order to preserve the number of the 1-arcs. We may also insert a labeled 1-arc in a k-noncrossing matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \delta^{ \prime \prime} \in { \cal G}_k ( s , m ) $$ \end{document} . In this case, we can only insert the 1-arc between two vertices not forming a 1-arc. Therefore, we arrive at (m + 1)g_k(s, m + 1) + (2s + 1 − m)g_k(s, m) different such labeled matchings and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} ( m + 1 ) g_k ( s + 1 , m + 1 ) = ( m + 1 ) g_k ( s , m + 1 ) + ( 2s + 1 - m ) g_k ( s , m ) . \tag{19} \end{align*} \end{document}

This recursion implies the following partial differential equation for the generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} x^ { - 1 } \frac { \partial { \bf G } _k ( x , y ) } { \partial y } = \frac { \partial { \bf G } _k ( x , y ) } { \partial y } + 2x \frac { \partial { \bf G } _k ( x , y ) } { \partial x } + { \bf G } _k ( x , y ) - y \frac { \partial { \bf G } _k ( x , y ) } { \partial y } , \tag { 20 } \end{align*} \end{document}

whose general solution is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _k ( x , y ) = \frac { F \left( \frac { yx - 1 - x } { \sqrt { x } } \right) } { \sqrt { x } } , \tag { 21 } \end{align*} \end{document}

where F(z) is an arbitrary function. By definition, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \sum\nolimits_{m = 0}^sg_k ( s , m ) = f_k ( 2s , 0 ) $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G}_k ( x , 1 ) = \sum_{s \geq 0}f_k ( 2s , 0 ) x^s. \tag{22} \end{align*} \end{document}

Using eq. (21) and eq. (22) we derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _k ( x , y ) = \frac { 1 } { x + 1 - yx } \sum_ { s \geq 0 } f_k ( 2s , 0 ) \left( \frac { x } { ( x + 1 - yx ) ^2 } \right) ^s , \tag { 23 } \end{align*} \end{document}

whence the lemma.   ▪

We now show how to derive the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape of a given k-noncrossing, σ-canonical RNA structures. This construction is based on the notion of k-noncrossing cores (Jin and Reidys, 2009). A k-noncrossing core is a k-noncrossing RNA structure in which each stack has size exactly one. The cores of a k-noncrossing, σ-canonical RNA structure, δ, denoted by c(δ) is obtained in two steps: first we map arcs and isolated vertices as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \forall \ell \geq \sigma - 1; \quad ( ( i - \ell , j + \ell ) , \ldots , ( i , j ) )\, \mapsto\, ( i , j ) \ { \rm and} \ j \,\mapsto\, j \ { \rm if} \ j \ { \rm is \ isolated} \tag{24} \end{align*} \end{document}

and second we relabel the vertices of the resulting diagram from left to right in increasing order (Fig.5). We are now in position to define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_k^5 $$ \end{document} -shapes.

OPEN IN VIEWER

FIG. 5.

A 3-noncrossing core structure is obtained from a 3-noncrossing, 1-canonical RNA structure in two steps.

Definition 1 ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf lv}_{\bf k}^{\bf 5} $$ \end{document} -shape)

A \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape is a k-noncrossing matching with stacks of size exactly one.

That is, given a k-noncrossing, σ-canonical RNA structure δ, its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_k^5 (\delta) $$ \end{document} , is obtained by first removing all isolated vertices and second collapsing all stacks into a single arc, (Fig. 6).

OPEN IN VIEWER

FIG. 6.

Generation of the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^5 $$ \end{document} -shape. A 3-noncrossing, 2-canonical RNA structure (top left) is mapped in two steps into its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^5 $$ \end{document} -shape (top right).

By construction, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} shapes do not preserve stack-lengths, unpaired regions, and interior loops, i.e., sequences of parallel arcs of the form \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} ( ( i_1 , j_1 ) , [ i_1 + 1 , i_2 - 1 ] , ( i_2 , j_2 ) , [ j_2 + 1 , j_1 - 1 ] ) , \end{align*} \end{document}

where (i₂, j₂) is an arc nested in (i₁, j₁) and [i, j] is an interval of unpair region.

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal I}_k ( s , m ) \,( i_k ( s , m ) ) $$ \end{document} denote the set (number) of the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \rm lv}_k^5$$ \end{document} -shapes of length 2s with m 1-arcs and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf I}_k ( z , u ) = \sum_{s \geq 0} \sum_{m = 0}^{s} i_k ( s , m ) z^su^m \tag{25} \end{align*} \end{document}

be the bivariate generating function. Furthermore, let i_k(s) denote the number of the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shapes of length 2s with generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf I}_k ( z ) = \sum_{s \geq0}i_k ( s ) z^s. \tag{26} \end{align*} \end{document}

Since any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape is in particular the core of some k-noncrossing matching, Lemma 1 allows us to establish a relation between the bivariate generating function of i_k(s, m) and the generating function of F _k (z).

Theorem 3

Let k, s, m be natural numbers where k ≥ 2, then the following assertions hold

(a) the generating functions I _k (z, u) and I _k (z) satisfy \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf I } _k ( z , u ) = \frac { 1 + z } { 1 + 2z - zu } { \bf F } _k \left( \frac { z ( 1 + z ) } { ( 1 + 2z - zu ) ^2 } \right) \tag{27} \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} {\bf I } _k ( z ) = { \bf F } _k \left( \frac { z } { 1 + z } \right) .\tag{28} \end{align*} \end{document}

(b) for 2 ≤ k ≤ 7, the number of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_k^5 $$ \end{document} -shapes of length 2s is asymptotically given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} i_k ( s ) \,\sim\, c_k s^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \mu_{k}^{ - 1} \right) ^{s} , \tag{29} \end{align*} \end{document}

where μ_k is the unique minimum positive real solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \frac { z } { 1 + z } = \rho_k^2 $$ \end{document} and c_k is some positive constant.

Proof

We first prove (a). For this purpose we define a map between k-noncrossing matchings with m 1-arcs and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_k^5 $$ \end{document} -shapes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} g : \ { \cal G}_k ( s , m ) \rightarrow \dot{ \bigcup_{0 \leq b \leq s - m}} \left[ { \cal I}_k ( s - b , m ) \times \left\{ ( a_j ) _{1 \leq j \leq s - b} \mid \sum_{j = 1}^{s - b}a_j = b , \ a_j \geq 0 \right\} \right] , \end{align*} \end{document}

where s ≥ 1. Here, for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \delta \in { \cal G}_k ( s , m ) $$ \end{document} , we have g(δ) = (c(δ), (a_j)_{1 ≤ j ≤ s − b}), where c(δ) is the core structure of δ obtained according to eq. (24) and where (a_j)_{1 ≤ j ≤ s − b} keeps track of the deleted arcs. It is straightforward to check that the map g is well defined, since all the 1-arcs of c(δ) are just the 1-arcs of δ. By construction, g is a bijection and then we have that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G}_k ( x , y ) = \sum_{s \geq 0} \sum_{m = 0}^sg_k ( s , m ) x^sy^m = \sum_{m \geq 0} \sum_{ \gamma \in { \cal I}_k ( m ) } { \bf G}_ \gamma ( x , y ) , \tag{30} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \cal I}_k ( m )$$ \end{document} is the set of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shapes having m 1-arcs and G _γ (x, y) is the generating function of all k-noncrossing matchings having m 1-arcs that are mapped into the shape γ. Suppose γ has s arcs. We consider the combinatorial classes of arcs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal R} $$ \end{document} and 1-arcs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal R}^* $$ \end{document} with generating functions R(x) = x and R^*(x, y) = yx. Then

each k-noncrossing matching having shape γ is obtained by inflating γ-arcs to stacks and the combinatorial class of stacks is given by

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \cal R} \times { \rm SEQ} ( { \cal R} ) \end{align*} \end{document}

the inflation of arcs does not affect the number of 1-arcs.

Therefore, we derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _ \gamma ( x , y ) = \left( \frac { x } { 1 - x } \right) ^s y^ { m } . \tag { 31 } \end{align*} \end{document}

For any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \gamma , \gamma_1 \in { \cal I}_k ( m ) $$ \end{document} , having s arcs we have G _γ (x, y) = G_γ1(x, y), whence \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _k ( x , y ) = \sum_ { m \geq 0 } \sum_ { \gamma \in { \cal I } _k ( m ) } { \bf G } _ \gamma ( x , y ) = \sum_ { s \geq 0 } \sum_ { m = 0 } ^ { s } i_k ( s , m ) \left( \frac { x } { 1 - x } \right) ^s y^m. \tag { 32 } \end{align*} \end{document}

According to Lemma 1, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf G } _k ( x , y ) = \frac { 1 } { x + 1 - yx } { \bf F } _k \left( \frac { x } { ( x + 1 - yx ) ^2 } \right) \end{align*} \end{document}

and setting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ z = \frac { x } { 1 - x } $$ \end{document} and u = y, we arrive substituting for G _k (x, y) in eq. (32) at \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf I } _k ( z , u ) = \frac { 1 + z } { 1 + 2z - zu } { \bf F } _k \left( \frac { z ( 1 + z ) } { ( 1 + 2z - zu ) ^2 } \right) . \end{align*} \end{document}

In particular, setting u = 1, we derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf I } _k ( z ) = { \bf F } _k \left( \frac { z } { 1 + z } \right) , \end{align*} \end{document}

whence (a) follows.

Assertion (b) is a direct consequence of the supercritical paradigm; see Proposition 1. As mentioned before, the ordinary generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf F}_k ( z ) = \sum\nolimits_{n \ge 0} f_k ( 2n , 0 ) z^{n} $$ \end{document} is D-finite (Stanley, 1980), and the inner function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \vartheta ( z ) = \frac { z } { 1 + z } $$ \end{document} is algebraic, satisfies ϑ(0) = 0 and is analytic for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid z \mid < 1 $$ \end{document} . By direct calculation, using the fact that all singularities of F _k (z) are contained within the set of zeros of q_0,k(z) (Table 1), we can then verify that F _k (ϑ(z)) has the unique dominant real singularity μ_k < 1 satisfying \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \vartheta ( \mu_k ) = \rho_k^2 $$ \end{document} for 2 ≤ k ≤ 7 by Maple (for online Supplementary Material, see www.liebertonline.com). In view of ϑ′(μ_k) ≠ 0, Proposition 1 guarantees eq. (29) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} i_k ( s ) \,\sim\, c_k s^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \mu_{k}^{ - 1} \right) ^{s}. \end{align*} \end{document}

This proves (b), completing the proof of the theorem.   ▪

We next studying the number of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_k^5 $$ \end{document} -shapes induced by k-noncrossing, σ-canonical RNA structures of fixed length n, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_{k , \sigma}^5 ( n ) $$ \end{document} , setting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv}_{k , \sigma}^5 ( x ) = \sum_{n \geq 0} { \rm lv}_{k , \sigma}^5 ( n ) x^n. \tag{33} \end{align*} \end{document}

Theorem 4

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ k , \sigma \in {\mathbb N} $$ \end{document} , where k ≥ 2. Then the following assertions hold

(a) the generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{k , \sigma}^5 ( x ) $$ \end{document} is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^5 ( x ) = \frac { ( 1 + x^ { 2 \sigma } ) } { ( 1 - x ) ( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } ) } { \bf F } _k \left( \frac { x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } \right) ^2 } \right) . \tag { 34 } \end{align*} \end{document}

(b) for 2 ≤ k ≤ 7 and 1 ≤ σ ≤ 10 \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv}_{k , \sigma}^5 ( n ) \sim c_{k , \sigma}n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \zeta_{k , \sigma}^{ - 1} \right) ^{n} , \tag{35} \end{align*} \end{document}

where c_k,σ > 0 and ζ_k,σ is the unique minimum positive real solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \frac { x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } \right) ^2 } = \rho_k^2. \tag { 36 } \end{align*} \end{document}

Proof

In order to prove (a), we observe that we can always inflate a structure by adding arcs to stacks or isolated vertices without changing its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape. In fact, for any given \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape, β, adding the minimal number of arcs to each stack such that every stack has σ arcs, and inserting one isolated vertex in any 1-arc, we derive a k-noncrossing, σ-canonical RNA structure having arc-length≥ 2, of minimal length. If a k-noncrosing, σ-canonical RNA structure of length n with a shape in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal I}_k ( s , m ) $$ \end{document} , then n ≥ 2σs + m. We can therefore derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{k , \sigma}^5 ( x ) $$ \end{document} , see eq.(33), from the bivariate generating function I _k (z, u) as follows \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^5 ( x ) = \sum_ { n \geq 0 } \sum_ { s = 0 } ^ { \lfloor \frac { n } { 2 \sigma } \rfloor } \sum_ { m = 0 } ^ { \min \{ s , n - 2 \sigma s \} } i_k ( s , m ) x^ { n } = \sum_ { s \geq 0 } \sum_ { m = 0 } ^ { s } \sum_ { n \geq 2 \sigma s + m } i_k ( s , m ) x^ { n } , \end{align*} \end{document}

whence \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^5 ( x ) = \frac { 1 } { 1 - x } \sum_ { s \geq 0 } \sum_ { m = 0 } ^ { s } i_k ( s , m ) x^ { 2 \sigma s + m } \end{align*} \end{document}

and in view of eq. (27), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf I } _k ( z , u ) = \frac { 1 + z } { 1 + 2z - zu } { \bf F } _k \left( \frac { z ( 1 + z ) } { ( 1 + 2z - zu ) ^2 } \right) $$ \end{document} , we derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^5 ( x ) = \frac { ( 1 + x^ { 2 \sigma } ) } { ( 1 - x ) ( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } ) } { \bf F } _k \left( \frac { x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } \right) ^2 } \right) . \end{align*} \end{document}

As for assertion (b), we observe that the factor \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \varphi_ \sigma ( x ) = \frac { x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } \right) ^2 } \end{align*} \end{document}

is algebraic and φ_σ(0) = 0. We verify that φ_σ(x) is for 1 ≤ σ ≤ 10 analytic when \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid x \mid < r_\sigma $$ \end{document} , where r_σ < 1 and furthermore \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \phi_ { \sigma } ( x ) = \frac { ( 1 + x^ { 2 \sigma } ) } { ( 1 - x ) ( 1 + 2x^ { 2 \sigma } - x^ { 2 \sigma + 1 } ) } \end{align*} \end{document}

is analytic for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid x \mid < r_\sigma $$ \end{document} . We distinguish the cases k > 2 and k = 2.

For 2 < k ≤ 7 and 1 ≤ σ ≤ 10, the minimum positive real solution of eq. (36), ζ_k,σ, is the unique dominant singularity of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{k , \sigma}^5 ( x ) $$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid \zeta_{k,\sigma}\mid < r_\sigma $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \varphi_ \sigma^{ \prime} ( \zeta_{k , \sigma} ) \neq 0 $$ \end{document} Therefore, Proposition 1 implies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv}_{k , \sigma}^5 ( n ) \,\sim\, c_{k , \sigma}n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \zeta_{k , \sigma}^{ - 1} \right) ^{n} , \end{align*} \end{document}

where c_k,σ is some positive constant. In case of k = 2, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf F } _2 ( z ) = \sum_ { n \geq 0 } f_2 ( 2n , 0 ) z^n = \frac { 2 } { 1 + \sqrt { 1 - 4 z } } . \tag { 37 } \end{align*} \end{document}

Substituting φ_σ(x) into the eq. (37), we observe that the poles of φ_σ(x) are not singularities of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{2 , \sigma}^5 (x) $$ \end{document} and the dominant singularity of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{2, \sigma}^5 (x) $$ \end{document} is the minimum positive solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \varphi_ \sigma ( x ) = \rho_2^2 $$ \end{document} . Employing Theorems 1 and 2, we derive eq. (35), and the proof of the theorem is complete.   ▪

4. Combinatorics Of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\rm lv}_{\rm k}^{\bf 1} $$ \end{document} -Shapes

Definition 2 ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\bf lv}_{\bf k}^{\bf 1} $$ \end{document} -shape)

A \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shape is a k-noncrossing structure in which each stack and each segment of isolated vertices have length exactly one.

That is, given a k-noncrossing, σ-canonical RNA structure its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^{ \rm 1} $$ \end{document} -shape is derived as follows: first we apply the core map, second we replace a segment of isolated vertices by a single isolated vertex and third relabel the vertices of the resulting diagram (Fig. 7). \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^{ \rm 1} $$ \end{document} -shapes do not preserve stack-lengths and project intervals of isolated vertices into singletons. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ {\cal J}_k $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal I}_k $$ \end{document} denote the set of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shapes, respectively. There is a map between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shapes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \phi: \quad{ \cal J}_k \rightarrow{ \cal I}_k , \tag{38} \end{align*} \end{document} OPEN IN VIEWER

FIG. 7.

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes via the core map and subsequent identification of unpaired nucleotides: A 3-noncrossing, 1-canonical RNA structure (top left) is mapped into its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^1 $$ \end{document} -shape (top middle). The \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^1 $$ \end{document} -shape is projected into its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^5 $$ \end{document} -shape (top right) via ϕ in two steps.

obtained by removing all isolated vertices from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes and then collapsing each stack into a single arc (Fig. 7). By construction, ϕ is surjective (for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape, we can, inserting one isolated vertex in any 1-arc, obtain a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shape).

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal J}_k ( n , h ) $$ \end{document} (j_k(n, h)) denote the set (number) of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes of length n having h-arcs, and let j_k(n) be the number of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes of length n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf J}_k ( z , u ) = \sum_{h \geq 0} \sum_{n = 2h}^{4h + 1}j_k ( n , h ) z^nu^h \quad { \rm and} \quad { \bf J}_k ( z ) = \sum_{n \geq 0}j_k ( n ) z^n. \tag{39} \end{align*} \end{document}

Theorem 5

For k, n, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ h \in \mathbb{N} $$ \end{document} , k ≥ 2, the following assertions hold

(a) the generating functions J _k (z, u) and J _k (z) are given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf J } _k ( z , u ) = \frac { ( 1 + z ) ( 1 + uz^2 ) } { uz^3 + 2uz^2 + 1 } { \bf F } _k \left( \frac { ( 1 + z ) ^2 ( 1 + uz^2 ) uz^2 } { ( uz^3 + 2uz^2 + 1 ) ^2 } \right) \tag{40} \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf J } _k ( z ) = \frac { ( 1 + z ) ( 1 + z^2 ) } { z^3 + 2z^2 + 1 } { \bf F } _k \left( \frac { ( 1 + z ) ^2 ( 1 + z^2 ) z^2 } { ( z^3 + 2z^2 + 1 ) ^2 } \right) . \tag{41} \end{align*} \end{document}

(b) for 2 ≤ k ≤ 7, the number of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \sf lv}_k^1 $$ \end{document} -shapes of length n satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} j_k ( n ) \,\sim\, c_k^{ \prime} n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \mu_{k}^{ \prime - 1} \right) ^{n} , \tag{42} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ c_{k}^{ \prime} > 0 $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mu_{k}^{ \prime} $$ \end{document} is the unique minimum positive real solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \frac { ( 1 + z ) ^2 ( 1 + z^2 ) z^2 } { ( z^3 + 2z^2 + 1 ) ^2 } = \rho_k^2. \tag { 43 } \end{align*} \end{document}

Proof

We prove (a) via symbolic enumeration noticing that we can represent an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shape as an inflation of an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shape. By definition of the map ϕ, the generating function J _k (z, u) can be rewritten as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf J}_k ( z , u ) = \sum_{m \geq0} \sum_{ \zeta \in{ \cal I}_k ( m ) }{ \bf{S}}_{ \zeta} ( z , u ) , \tag{44} \end{align*} \end{document}

where S_ζ(z, u) is the generating function of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes whose images of ϕ are ζ and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal I}_k ( m ) $$ \end{document} denotes the set of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^5 $$ \end{document} -shapes with m 1-arcs. For any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \zeta \in { \cal I}_k ( s, m ) $$ \end{document} , we can inflate it to a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes by the following steps (Fig. 8).

we inflate each arc of the shape to a stem of stacks of size 1. Between stacks we can insert isolated vertices to the left or the right, or on both sides in order to separate the stacks and for each such insertion exactly one isolated vertex is used.

we insert at most one isolated vertex in any of the remaining (2s + 1) positions. Furthermore, one isolated vertex is inserted into each 1-arc.

OPEN IN VIEWER

FIG. 8.

An \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^5 $$ \end{document} -shape (left) is inflated to an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_3^1 $$ \end{document} -shape (right) in two steps. In (1), we add stacks of size one. Stacks are separated by isolated vertices to the left (blue) or both sides (red). In (2), we insert at most one isolated vertex (red) at the remaining positions.

We call the newly added stacks of size 1 induced. We introduce the combinatorial classes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal E} $$ \end{document} (neutral class which include only one element of size 0), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal Z} $$ \end{document} (vertex), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal R} $$ \end{document} (arc), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal N} $$ \end{document} (induced stacks), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal M} $$ \end{document} (stems), and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal S}_{ \zeta} $$ \end{document} ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shapes whose images are ζ under ϕ), where E(z) = 1, Z(z) = z, R(z, u) = uz². \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \cal S}_{ \zeta} = \left( { \cal M} \right) ^s \times \left( { \cal E} + { \cal Z} \right) ^{2s + 1 - m} \times \left( { \cal Z} \right) ^{m} , \tag{45} \end{align*} \end{document}

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \cal M} = { \cal R} \times { \rm SEQ} \left({\cal N} \right) , \tag{46} \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \cal N} = { \cal R} \times \left( { \cal Z}+ { \cal Z} + { \cal Z}^2 \right) , \tag{47} \end{align*} \end{document}

Thus, the generating function S _ζ (z, u) is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf { S } } _ { \zeta } ( z , u ) = \left( \frac { uz^2 } { 1 - uz^2 ( 2z + z^2 ) } \right) ^s ( 1 + z ) ^ { 2s + 1 - m } z^m , \tag { 48 } \end{align*} \end{document}

By construction, for any two shapes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \zeta_1 , \zeta_2 \in {\cal I} ( s , m ) $$ \end{document} we have S_ζ1(z, u) = S_ζ2(z, u), whence \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf J}_k ( z , u ) = \sum_{s \geq0} \sum_{m = 0}^{s}i_k ( s , m ) { \bf{S}}_{ \zeta} ( z , u ) . \tag{49} \end{align*} \end{document}

According to Theorem 3, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \sum_ { s \geq0 } \, \sum_ { m = 0 } ^ { s } i_k ( s , m ) x^s y^m = \frac { 1 + x } { 1 + 2x - xy } { \bf F } _k \left( \frac { x ( 1 + x ) } { ( 1 + 2x - xy ) ^2 } \right) . \end{align*} \end{document}

Therefore, substituting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} x = \frac { uz^2 ( 1 + z ) ^2 } { 1 - uz^2 ( 2z + z^2 ) } \quad { \rm and } \quad y = \frac { z } { 1 + z } \end{align*} \end{document}

into eq. (49), we derive eq. (40). In particular, setting u = 1, we derive J _k (z), whence assertion (a).

Assertion (b) follows in complete analogy to the proof of Theorem 4. First we note that the factor \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \tau ( z ) = \frac { ( 1 + z ) ^2 ( 1 + z^2 ) z^2 } { ( z^3 + 2z^2 + 1 ) ^2}\tag{50} \end{align*} \end{document}

is algebraic and τ(0) = 0. We next verify that τ(z) is analytic for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid z \mid < r^\prime $$ \end{document} , where r′ < 1 and the unique dominant singularity of J _k (z) is the minimum positive real solution \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mu_{k}^{ \prime} $$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \frac { ( 1 + z ) ^2 ( 1 + z^2 ) z^2 } { ( z^3 + 2z^2 + 1 ) ^2 } = \rho_k^2 \end{align*} \end{document}

for 2 ≤ k ≤ 7, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \mid \mu_{k}^{ \prime} \mid < r^{ \prime} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \tau^{ \prime} ( \mu_{k}^{ \prime} ) \neq 0 $$ \end{document} (for online Supplementary Material, see www.liebertonline.com). Now (b) follows from Proposition 1.   ▪

We finally compute the number of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^1_k $$ \end{document} -shapes induced by k-noncrossing, σ-canonical RNA structures of fixed length n, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_{k , \sigma}^1 ( n ) $$ \end{document} . Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv}^1_{k , \sigma} ( x ) = \sum_{n \geq 0} { \rm lv}_{k , \sigma}^1 ( n ) x^n. \tag{51} \end{align*} \end{document}

Theorem 6

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ k , \sigma \in {\mathbb N} $$ \end{document} , where k ≥ 2. Then the following assertions hold

(a) the generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}^1_{k , \sigma} ( x ) $$ \end{document} is given by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } ^1_ { k , \sigma } ( x ) = \frac { ( 1 + x ) ( 1 + x^ { 2 \sigma } ) } { ( 1 - x ) ( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 ) } { \bf F } _k \left( \frac { ( 1 + x ) ^2x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 \right) ^2 } \right) .\tag { 52 } \end{align*} \end{document}

(b) for 2 ≤ k ≤ 7 and 1 ≤ σ ≤ 10, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv}^1_{k , \sigma} ( n ) \,\sim\, c^\prime_{k , \sigma} n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \chi_{k , \sigma}^{ - 1} \right) ^{n} ,\tag{53} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ c_{k , \sigma}^{ \prime} > 0 $$ \end{document} and χ_{k ,σ} is the unique minimum positive real solution of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \frac { ( 1 + x ) ^2x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 \right) ^2 } = \rho_k^2.\tag { 54 } \end{align*} \end{document}

Proof

Obviously, we can inflate any structure by adding arcs into its stacks or duplicating isolated vertices without changing its \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shape. As a result, we can derive from any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_k^1 $$ \end{document} -shape by inflating its stacks to σ arcs, a unique, minimal, k-noncrossing, σ-canonical RNA structure inducing it. If a k-noncrosing, σ-canonical RNA structure of length n has a shape in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \cal J}_k ( s , h ) $$ \end{document} , then we have n ≥ 2h(σ − 1) + s. We can use this observation to conclude \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv } _ { k , \sigma } ^1 ( n ) = \sum_ { h = 0 } ^ { \lfloor \frac { n } { 2 \sigma } \rfloor } \sum_ { s = 2h } ^ { \min \{ 4h + 1 , n - 2 ( \sigma - 1 ) h \} } j_k ( s , h ) . \end{align*} \end{document}

Accordingly, we can rewrite the generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^1 ( x ) = \sum_ { h \geq 0 } \sum_ { s = 2h } ^ { 4h + 1 } \sum_ { n \geq 2h ( \sigma - 1 ) + s } j_k ( s , h ) x^ { n } = \frac { 1 } { 1 - x } \sum_ { h \geq 0 } \sum_ { s = 2h } ^ { 4h + 1 } j_k ( s , h ) x^ { 2h ( \sigma - 1 ) + s } . \end{align*} \end{document}

Employing eq. (40), we derive \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \bf Lv } _ { k , \sigma } ^1 ( x ) = \frac { ( 1 + x ) ( 1 + x^ { 2 \sigma } ) } { ( 1 - x ) ( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 ) } { \bf F } _k \left( \frac { ( 1 + x ) ^2x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 \right) ^2 } \right) \end{align*} \end{document}

and assertion (a) follows. As for assertion (b), we proceed in analogy to the proof of Theorem 4. We verify that for 2 ≤ k ≤ 7 and 1 ≤ σ ≤ 10, the unique minimum positive real solution, χ_k,σ, of eq. (54) is the unique dominant singularity of generating function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \bf Lv}_{k , \sigma}^1 ( x ) $$ \end{document} and that the derivative of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} \frac { ( 1 + x ) ^2x^ { 2 \sigma } ( 1 + x^ { 2 \sigma } ) } { \left( x^ { 2 \sigma + 1 } + 2x^ { 2 \sigma } + 1 \right) ^2 } \end{align*} \end{document}

is nonzero at z = χ_k,σ. Consequently, Proposition 1 implies that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv}_{k , \sigma}^1 ( n ) \,\sim\, c_{k , \sigma}^{ \prime} n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \chi_{k , \sigma}^{ - 1} \right) ^{n} , \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ c_{k , \sigma}^{ \prime} $$ \end{document} is some positive constant, whence (b) and the theorem is proved.   ▪

5. Conclusion

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_{k}^1 $$ \end{document} - and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}_{k}^5 $$ \end{document} -shapes of k-noncrossing, σ-canonical RNA pseudoknot structures provide a significant simplification of complicated molecular configurations with cross-serial interactions. The asymptotic formulas presented in Theorems 4 and 6 \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} \begin{align*} { \rm lv}_{k , \sigma}^5 ( n )\, & \sim\, c_{k , \sigma}n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \zeta_{k , \sigma}^{ - 1} \right) ^{n} \\ { \rm lv}^1_{k , \sigma} ( n )\, & \sim\, c_{k , \sigma}^{ \prime} n^{ - ( ( k - 1 ) ^2 + ( k - 1 ) / 2 ) } \left( \chi_{k , \sigma}^{ - 1} \right) ^{n} , \end{align*} \end{document}

imply all asymptotic results on abstract shapes of secondary structures in the literature (note that for k = 2, we have n^{−((k − 1)2 + (k − 1)/2)} = n^−3/2).

The growth rates of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^1_{k} $$ \end{document} - and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^5_{k} $$ \end{document} -shapes of k-noncrossing, σ-canonical RNA structures, are displayed in Tables 2, 3, 4 and 5, where they are contrasted with the exponential growth rates of k-noncrossing, σ-canonical RNA structures, γ_k,σ.

OPEN IN VIEWER

Table 2.

Exponential Growth Rates \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \zeta_{k , \sigma}^{-1} $$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${\rm lv}_{ \rm k}^{5}$$ \end{document} -Shapes Induced by k-Noncrossing, σ-Canonical RNA Structures of Length n

σ/k	2	3	4	5	6	7
1	1.51243	3.67528	5.77291	7.82581	9.85873	11.88118
2	1.26585	1.93496	2.41152	2.80275	3.14338	3.44943
3	1.17928	1.55752	1.80082	1.98945	2.14693	2.28376

OPEN IN VIEWER

Table 3.

Exponential Growth Rates \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\chi_{k , \sigma}^{-1}$$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \rm lv}_{ \rm k}^{1}$$ \end{document} -Shapes Induced by k-Noncrossing, σ-Canonical RNA Structures of Length n

σ/k	2	3	4	5	6	7
1	2.09188	4.51263	6.65586	8.73227	10.7804	12.8137
2	1.56947	2.31767	2.81092	3.21184	3.55939	3.87079
3	1.38475	1.80408	2.05600	2.24968	2.41081	2.55050

OPEN IN VIEWER

Table 4.

Exponential Growth Rates of Arbitrary k-Noncrossing, 2-Canonical RNA Structures of Length n and the Numbers of Their Induced \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \rm lv}_{ \rm k}^{1}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \rm lv}_{ \rm k}^{5}$$\end{document} Shapes

k	2	3	4	5	6	7
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \gamma}_{k , 2}^{ - 1} $$ \end{document}	1.96798	2.58808	3.03825	3.41383	3.74381	4.04195
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \chi_{k , 2}^{ - 1} $$ \end{document}	1.56947	2.31767	2.81092	3.21184	3.55939	3.87079
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \zeta_{k , 2}^{ - 1} $$ \end{document}	1.26585	1.93496	2.41152	2.80275	3.14338	3.44943

OPEN IN VIEWER

Table 5.

Exponential Growth Rates of Arbitrary k-Noncrossing, 3-Canonical RNA Structures of Length n and the Numbers of Their Induced \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^1_{k} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $${ \rm lv}^5_{k}$$ \end{document} Shapes

k	2	3	4	5	6	7
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \gamma_{k , 3}^{ - 1} $$ \end{document}	1.71599	2.04771	2.27036	2.44664	2.59554	2.72590
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \chi_{k , 3}^{ - 1} $$ \end{document}	1.38475	1.80408	2.05600	2.24968	2.41081	2.55050
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ \zeta_{k , 3}^{ - 1} $$ \end{document}	1.17928	1.55752	1.80082	1.98945	2.14693	2.28376

Table 5 shows that the exponential growth rate of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^5_3 $$ \end{document} -shapes of k-noncrossing 3-canonical structures are significantly smaller than that of all k-noncrossing 3-canonical structures. Therefore, the abstract \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6} \begin{document} $$ { \rm lv}^5_k $$ \end{document} -shapes represent a meaningful reduction. Supplementary Material is available online at www.liebertonline.com.