Combinatorics of RNA-RNA interaction

RNA-RNA binding is an important phenomenon observed for many classes of non-coding RNAs and plays a crucial role in a number of regulatory processes. Recently several MFE folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Here joint structure means that in a diagram representation the intramolecular bonds of each partner are pseudoknot-free, that the intermolecular binding pairs are noncrossing, and that there is no so-called ``zig-zag'' configuration. This paper presents the combinatorics of RNA interaction structures including their generating function, singularity analysis as well as explicit recurrence relations. In particular, our results imply simple asymptotic formulas for the number of joint structures.


Introduction
RNA-RNA binding is an important phenomenon observed in various classes of noncoding RNAs and plays a crucial role in a number of regulatory processes. Examples include the regulation of translation in both: prokaryotes (Narberhaus et al., 2007) and eukaryotes (McManus et al., 2002;Banerjee et al., 2002), the targeting of chemical modifications (Bachellerie et al., 2002), insertion editing (Benne, 1992), and transcriptional control (Kugel and Goodrich, 2007). More and more evidence suggests, that RNA-RNA interactions also play a role for the functionality of long mRNA-like ncRNAs. A common theme in many RNA classes, including miRNAs, snRNAs, gRNAs, snoRNAs, and in particular many of the procaryotic small RNAs, is the formation of RNA-RNA interaction structures that are much more complex than simple complementary sense-antisense interactions. The interaction between two RNAs is governed by the same physical principles that determine RNA folding: the formation of specific base pairs patterns whose energy is 19.0%

28.4%
largely determined by base pair stacking and loop strains. Therefore, secondary structures are an appropriate level of description to quantitatively understand the thermodynamics of RNA-RNA binding.
By restricting the space of allowed configurations, polynomial-time algorithms on secondary structure level have been derived. (Pervouchine, 2004) and (Alkan et al., 2006) proposed MFE folding algorithms for predicting the joint structure of two interacting RNA molecules. In this model, "joint structure" means that the intramolecular structures of each partner are pseudoknot-free, that the intermolecular binding pairs are noncrossing, and that there is no so-called "zig-zag" configuration, see Section 3 for details. This structure class seems to include all major interaction complexes. The optimal joint structure can be computed in O(N 6 ) time and O(N 4 ) space by means of dynamic programming (Alkan et al., 2006;Pervouchine, 2004;Huang et al., 2010;Chitsaz et al., 2009). More recently, extensions involving the partition function were proposed by (Chitsaz et al., 2009) (piRNA) and (Huang et al., 2009) (rip), see Fig. 1.
In contrast to the situation for RNA secondary structures (Waterman et al., 1978;Schmitt et al., 1994), little is known about the joint structures that are the folding targets of rip (Huang et al., 2010). This paper closes this gap and introduces the combinatorics of interaction structures. We present the generating function of joint structures, its singularity analysis as well as explicit recurrence relations. In particular, our results imply simple formulas for the asymptotic number of joint structures.
The paper is organized as follows: in Section 2 we provide several basic fact and context. In Section 3 we introduce joint structures along the lines of (Huang et al., 2009). In Section 4 we follow the ideas of the paper  and consider shapes of joint structures. In Section 5 we use shapes in order to compute the generating function of joint structures and Section 6 deals with the singularity analysis. We then integrate our results in Section 7. Finally we present additional results in Section 8.

Some basic facts
2.1. Singularity analysis. Let f (z) = n≥0 a n z n be a generating function with nonnegative coefficients and a radius of convergence R > 0. In light of the fact that explicit formulas for the coefficients a n can be very complicated or even impossible to obtain, we switch over to investigate the estimation of a n in terms of the exponential factor γ and the subexponential factor P (n), that is, a n ∼ P (n) γ n . The derivation of exponential growth rate and subexponential factor is mainly based on singularity analysis. Singularity analysis is a framework that allows to analyze the asymptotics of these coefficients. The key to obtain the asymptotic information about the coefficients of a generating function is its dominant singularities, which raises the question on how to locate them. In the particular case of power series with nonnegative coefficients and a radius of convergence R > 0, a theorem of Pringsheim (Flajolet, 2007;Titchmarsh, 1939), guarantees a positive real dominant singularity at z = R. As we are dealing here with combinatorial generating functions we always have this dominant singularity. Furthermore for all our generating functions it is the unique dominant singularity. The class of theorems that deal with the deduction of information about coefficients from the generating function are called transfer-theorems (Flajolet, 2007). To be precise, we say a function f (z) is ∆ ρ analytic at its dominant singularity z = ρ, if it analytic in some domain ∆ ρ (φ, r) = {z | |z| < r, z = ρ, |Arg(z − ρ)| > φ}, for some φ, r, where r > |ρ| and 0 < φ < π 2 . We use the notation where c is some constant. Let [z n ]f (z) denote the coefficient of z n in the power series expansion of f (z) at z = 0. Since the Taylor coefficients have the property We can, without loss of generality, reduce our analysis to the case where z = 1 is the unique dominant singularity. The next theorem transfers the asymptotic expansion of a function around its unique dominant singularity to the asymptotic of the function's coefficients.
Theorem 1. (Flajolet, 2007) Let f (z) be a ∆ 1 analytic function at its unique dominant singularity z = 1. Let That is we have in the intersection of a neighborhood of 1 (2.1) f (z) = Θ(g(z)) for z → 1.
Then we have Theorem 2. (Flajolet, 2007) 2.2. Symbolic Enumeration. Symbolic enumeration (Flajolet, 2007) plays an important role in the following computations. We first introduce the notion of a combinatorial class. Let z = (z 1 , . . . , z d ) be a vector of d formal variables and k = (k 1 , . . . , k d ) be a vector of integers of the same dimension. We use the simplified notation Definition 1. A combinatorial class of d dimension, or simply a class, is an ordered pair (A, w A ) where A is a finite or denumerable set and a size-function w A : Given a class (A, w A ), the size of an element a ∈ A is denoted by w A (a), or simply w(a). We consistently denote by A n the set of elements in A that have size n and use the same group of letters for the cardinality A n = |A n |. The sequence {A n } is called the counting sequence of class A. The generating function of a class (A, w A ) is given by There are two special classes: E and Z i which contain only one element of size 0 and e i , respectively. In particular, the generating functions of the classes E and Z i are E(z) = 1 and Z i (z) = z i .
We adhere in the following to a systematic naming convention: classes, their counting sequences, and their generating functions are systematically denoted by the same groups of letters: for instance, C for a class, {C n } for the counting sequence, and C(z) for its generating function. Let A and B be combinatorial classes of d dimension. Suppose A i are combinatorial classes of 1 dimension. We define Plainly, Seq(A) defines a proper combinatorial class if and only if A contains no element of size 0. We immediately observe Proposition 1. Suppose A, B and C are combinatorial classes of d dimension having the generating functions A(z), B(z) and C(z). Let A i be combinatorial classes of 1 dimension having the generating functions A i (z). Then 2.3. Secondary structures. Let f (n) denote the number of all noncrossing matchings of n arcs having generating function Let T σ denote the combinatorial class of σ-canonical secondary structures having arclength ≥ 2 and T σ (n) denote the number of all σ-canonical secondary structures with n vertices having arc-length ≥ 2 and Since F(z) is algebraic and u σ (z) is a rational function, Theorem 3 implies that T σ (z) is an algebraic function for any σ.

Joint Structures
Given two RNA sequences R and S with n and m vertices, we index the vertices such that R 1 is the 5 ′ end of R and S 1 is the 3 ′ end of S. We refer to the ith vertex in R by R i and the subgraph induced by The intramolecular base pair can be represented by an arc (interior), with its two endpoints contained in either R or S. Similarly, the extramolecular base pair can be represented by an arc (exterior) with one of its endpoints contained in R and the other in S. A pre-structure, G(R, S, I), is a graph consisting of two secondary structures R and S with a set I of noncrossing exterior arcs. When representing arc-configurations, we draw all R-arcs in the upper-halfplane and all S-arcs in the lower-halfplane, see Fig. 2, (A).
. A zigzag is a subgraph containing two dependent interior arcs R i 1 R j 1 and S i 2 S j 2 neither one subsuming the other, see  . Ancestors and descendants: for the exterior arc R 5 S 5 , we have the following sets of R-ancestors and S-ancestors of The exterior arc R 5 S 5 is a common descendant of R 1 R 15 and S 3 S 9 , while R 10 S 17 is not. Subsumed arcs: R 1 R 15 subsumes S 3 S 9 and S 1 S 21 . (B): A zigzag, generated by R 2 S 1 , R 3 S 3 and R 5 S 4 . structures of the size (n, m, h) and set the counting sequence J(n, m, h) = |J(n, m, h)|. The generating function of the class J is given by We next specify some notation • an interior arc (or simply arc) of length λ is an arc R • an interior stack (or simply stack) of length σ is a maximal sequence of "parallel" interior arcs, • an exterior stack of length τ is a maximal sequence of "parallel" exterior arcs, σ,τ denote the class of all joint structures with arc-length ≥ λ, interior stack-length ≥ σ, exterior stack-length ≥ τ . Similarly, we can define its counting sequence J [λ] σ,τ (n, m, h) and generating function J [λ] σ,τ (x, y, z). In case of λ = 2, we omit λ in the notation. If there is no restriction on the interior and exterior stack-length, we also omit further indices. In the particular case σ = τ , we just write σ in the notation and omit τ . In Fig. 2, (A), we give an example of joint structure with arc-length ≥ 3, interior stack-length ≥ 2 and exterior stack-length ≥ 3.
We denote the subgraph of a joint structure J(R, S, I) induced by a pair of subse- Given a joint structure J(R, S, I), a tight structure of J(R, S, I) is the minimal block J i,j;i ′ ,j ′ containing all the R-ancestors and S-ancestors of any exterior arc in J i,j;i ′ ,j ′ and all the descendants of any interior arc in J i,j;i ′ ,j ′ . In the following, a tight structure is denoted by J T i,j;i ′ ,j ′ . In particular, we denote the joint structure J(R, S, I) by J T (R, S, I) if J(R, S, I) is a tight structure of itself. For any joint structure, there are only four types of tight structures are defined as follows: The key function of tight structures is that they are the building blocks for the decomposition of joint structures.
Proposition 2. (Huang et al., 2009) Let J(R, S, I) be a joint structure. Then (1) any exterior arc R k S k ′ in J(R, S, I) is contained in a unique tight structure.
(2) J(R, S, I) decomposes into a unique collection of tight structures and maximal secondary segments.

Shapes
Definition 2. (Shape) A shape is a joint structure containing no secondary segments in which each interior stack and each exterior stack have length exactly one.
Let G denote the combinatorial class of shapes. Given a joint structure, we can obtain its shape by first removing all secondary segments and second collapsing any stacks into a single arc. That is, we have a map ϕ : J → G, see Fig. 3. Let G(t 1 , t 2 , h) denote the number of shapes having t 1 arcs in the top sequence, t 2 arcs in the bottom and h exterior arcs having the generating function We next introduce tight shapes, double tight shapes, interaction segments, closed shapes and right closed shapes: • A tight shape is tight as a structure. Let G T denote the class of tight shapes by and G T (t 1 , t 2 , h) denote the number of tight shapes having t 1 arcs in the top sequence, t 2 arcs in the bottom and h exterior arcs having the generating function Any tight shape, comes as exactly one of the four types {•, ▽, △, }. The corresponding classes and generating functions are defined accordingly, G {•,▽,△, } and G {•,▽,△, } (x, y, z) respectively, • A double tight shape is a shape whose leftmost and rightmost blocks are tight structures. Let G DT denote the class of double tight shapes by and G DT (t 1 , t 2 , h) denote the number of double tight shapes having t 1 arcs in the top sequence, t 2 arcs in the bottom and h exterior arcs having the generating function • A closed shape is a tight shape of type {▽, △, }. Let G C denote the class of closed shapes and G C (t 1 , t 2 , h) denote the number of closed shapes having t 1 arcs in the top sequence, t 2 arcs in the bottom and h exterior arcs having the generating function • A right closed shape is a shape whose rightmost block is a closed shape rather than an exterior arc. Let G RC denote the class of right close shapes and G RC (t 1 , t 2 , h) denote the number of right close shapes having t 1 arcs in the top sequence, t 2 arcs in the bottom and h exterior arcs having the generating function • In a shape, an interaction segment is an empty structure or an tight structure of type • (an exterior arc). We denote the class of interaction segment by I and the associated generating function by I(x, y, z). Obviously, I(x, y, z) = 1 + z.
Theorem 4. The generating function G(u, v, z) of shapes satisfies Proof. Proposition 2 implies that any shape can be decomposed into a unique collection of tight shapes. Furthermore, each shape can be decomposed into a unique collection of close shapes and exterior arcs. We decompose a shape in four steps, see Fig. 4. We translate each decomposition step into the construction of combinatorial classes in the language of symbolic enumeration.
Step (1): we decompose a shape into a right closed shape and rightmost interaction segment. We generate G = G RC × I + I. It follows from Proposition 1 that (4.3) G(x, y, z) = G RC (x, y, z) · I(x, y, z) + I(x, y, z).
Step (2): we decompose a right closed shape into the rightmost closed shape and the rest, deriving Step (3): we decompose a closed shape depending on its type. The decomposition operation in this step can be viewed as the "removal" of an interior arc. We derive and obtain the generating functions (4.5) G (x, y, z) = x y z + x y G DT (x, y, z).
Step (4): the class of double tight shapes arising from Step (3) can be obtained by excluding the class of interaction segment and the class of closed shapes from the class of shapes. Similarly, we have The corresponding generating function accordingly satisfies We proceed by solving the set of equations (4.3)-(4.6), thereby deriving the functional equation eq. (4.2) for G(x, y, z) and the theorem follows.

The generating function
We proceed by generating joint structures from shapes via inflation. Let J σ,τ denote the class of joint structures with arc-length ≥ 2, interior stack-length ≥ σ, exterior stacklength ≥ τ . Let J σ,τ (n, m, h) denote the number of joint structures in J σ,τ having n vertices in the top, m vertices in the bottom and h exterior arcs having the generating function J σ,τ (x, y, z) = J σ,τ (n, m, h) x n y m z h .
Theorem 5. For σ ≥ 1, τ ≥ 1 , we have Proof. Let G(t 1 , t 2 , h) denote the class of shapes having t 1 interior arcs in the top, t 2 interior arcs in the bottom and h exterior arcs. For any joint structure, we can obtain a unique shape in G as follows: (1) Remove all secondary segments. (2) Contract each interior stack into one interior arc and each exterior stack into one exterior arc.
Then we have the surjective map ϕ : J σ,τ → G.

Fig. 5.
Step I: a shape (left) is inflated to a joint structure with arc-length ≥ 2 and interior stack-length ≥ 2. First, each interior arc in the shape is inflated to a stack of size at least two (middle). Then the shape is inflated to a new joint structure with arc-length ≥ 2 and interior stack-length ≥ 2 (right) by adding one stack of size two. Note that there are three ways to insert the secondary segments to separate the induced stacks (red).
We proceed by computing the generating function J γ (x, y, z). We will construct J γ (x, y, z) via simpler combinatorial classes as building blocks considering M σ (stems), K σ (stacks), N σ (induced stacks), R (interior arcs) and T σ (secondary segments). We inflate a shape γ ∈ G(t 1 , t 2 , h) to a joint structure in three steps.
Step I: we inflate any interior arc in γ to a stack of size at least σ and subsequently add additional stacks. The latter are called induced stacks and have to be separated by means of inserting secondary segments, see Fig. 5. Note that during this first inflation step no secondary segments, other than those necessary for separating the nested stacks are inserted. We generate • secondary segments T σ having stack-length ≥ σ having the generating function T σ (z), • interior arcs R with generating function R(z) = z 2 , • stacks, i.e. pairs consisting of the minimal sequence of arcs R σ and an arbitrary extension consisting of arcs of arbitrary finite length having the generating function • induced stacks, i.e. stacks together with at least one secondary segment on either or both of its sides, • stems, that is pairs consisting of stacks K σ and an arbitrarily long sequence of induced stacks having the generating function .
Note that we inflate both: top as well as bottom sequences. The corresponding generating function is Step II: we inflate any exterior arc in γ to an exterior stack of size at least τ and subsequently add additional exterior stacks. The latter are called induced exterior stacks and have to be separated by means of inserting secondary segments, see Fig. 6. Note that during this exterior-arc inflation step no secondary segments, other than those necessary for separating the stacks are inserted. We generate • exterior arc R 0 having the generating function • exterior stacks, i.e. pairs consisting of the minimal sequence of exterior arcs R τ 0 and an arbitrary extension consisting of exterior arcs of arbitrary finite length Step II: a joint structure (left) obtained in (1) in Fig. 5 is inflated to a joint structure in J 2,2 . First, each exterior arc in the joint structure is inflated to an exterior stack of size at least two (middle), and then the structure is inflated to a new joint structure in J 2,2 (right) by adding one exterior stack of size two. There are three ways to insert the secondary segments to separate the induced exterior stacks (red).
having the generating function • induced exterior stacks, i.e. stacks together with at least one secondary segment on either or both its sides, having generating function Step III: a joint structure (left) obtained in (1) in Fig. 6 is inflated to a new joint structure in J 2,2 (right) by adding secondary segments (red).
• exterior stems, that is pairs consisting of exterior stacks K ′ τ and an arbitrarily long sequence of induced exterior stacks having the generating function .
We inflate all the exterior arcs and the corresponding generating function is Step III: here we insert additional secondary segments at the remaining (2t 1 + h + 1) positions in the top and the (2t 2 + h + 1) positions in the bottom, see Fig. 7. Formally, the third inflation is expressed via the combinatorial class where the corresponding generating function is

Combining
Step I, Step II and Step III we arrive at and accordingly Therefore, .
Solving this functional equation, we derive It is straightforward to verify that the dominant singularity ρ of U(z) is the minimal and positive real solution of 1 − 2z − 9z 2 − 10z 3 − 3z 4 = 0 and ρ ≈ 0.22144, see Fig. 8. For our computations the following instance of the supercritical paradigm (Flajolet, 2007) is of central importance: 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).  Fig. 8. Universality of the square root. We display the dominant singularity of the generating function U(z) of shapes (here at ρ ≈ 0.22144). All singularities arising from composition of the "outer" function U(z) governed by the supercritical paradigm produce this type of singularity, leading to the subexponential factor n − 3 2 .
Proof. Since ϑ(z) is an algebraic function such that ϑ(0) = 0 and U(z) is algebraic whence is D-finite, we can conclude that the composition U(ϑ(z)) is D-finite. In particular U(ϑ(z)) has a singular expansion. Next, we calculate the singular expansion of the composite function U(ϑ(z)). In view of [z n ]f (z) = γ n [z n ]f ( z γ ) it suffices to analyze the function U(ϑ(γz)) and to subsequently rescale in order to obtain the correct exponential factor. For this purpose we set where ϑ(z) is analytic in |z| ≤ r. Consequently ϑ(z) is analytic in |z| < r, for some 1 < r.
As for the singular expansion of U( ϑ(z)), substituting eq. (6.3) into the singular expansion of U(z), for z → 1, By Theorem 1 and Theorem 2 we arrive at for some constant c.
Finally, we use the scaling property of Taylor expansions in order to derive [z n ]U(ϑ(z)) = γ −1 n [z n ]U( ϑ(z)) and the proof is complete.
We remark that Lemma 1 allows under certain conditions to obtain the asymptotics of the coefficients of supercritical compositions of the "outer" function U(z) and "inner" function ϑ(z). The scenario considered here is tailored for asymptotic expressions of J σ (s).
6.2. Asymptotics of J σ (s). In this section we shall assume σ = τ . Let J σ (s) denote the number of joint structures of total s vertices having arc-length ≥ 2, stack-length ≥ σ and exterior stack-length ≥ σ having the generating function By definition, we have J σ (z) = J σ,σ (z, z, 1).
Proof. By Theorem 5 and the definition, we have .
Since T σ (z) is algebraic, we can conclude that ζ(z) is algebraic from the closure property of algebraic functions, whence U(ζ(z)) and J σ (z) are D-finite. Pringsheim's Theorem (Titchmarsh, 1939) guarantees that J σ (z) has a dominant real positive singularity γ σ . We verify that for 1 ≤ σ ≤ 9, the minimal, positive real solution of the equation ζ(z) = ρ is strictly smaller than the singularity of ζ(z), which is actually the singularity of T σ (z). Hence γ σ is the unique, minimal, positive real solution of the equation ζ(z) = ρ and it is straightforward to check that ζ ′ (z)| z=γσ = 0. Therefore the composite function U(ζ(z)) is governed by the supercritical paradigm of Lemma 1. Furthermore T σ (z) is analytic at γ σ , whence the subexponential factors of T σ (z) 2 U(ζ(z)) coincide with those of the function U(z). Consequently, The values of γ −1 σ are listed in Table 1. It remains to calculate the constant coefficient in the asymptotic formula. Setting the singular expansion of U(z) around ρ and the Taylor expansions of ζ(z) and T σ (z) 2 around γ σ , We proceed by substituting these expansions into T σ (z) 2 U(ζ(z)) Using Theorem 1 and Theorem 2, we have , we compute c 1 ≈ 1.6527921 and c 2 ≈ 4.3011932, completing the proof of Theorem 6.
We next observe that eq. (6.4) allows us to derive a functional equation for J σ (z), which in turn gives a recurrence of J σ (s).
Corollary 1. For σ ≥ 1, the generating function J σ (z) satisfies the functional equation Furthermore, the number J σ (s) of joint structures with total s vertices satisfies the following recurrence: where a(s), b(s) and c(s) are the coefficients of z s of A(z), B(z) and C(z), respectively.
In Fig. 9, we show that our asymptotic formulas work well already for small sequence length. Here we contrast the exact values, J 1 (s) and J 2 (s), with the asymptotic formulas given via Theorem 6: J 1 (s) ∼ c 1 s − 3 2 3.48766 s and J 2 (s) ∼ c 2 s − 3 2 2.24338 s .

Discussion
The discovery of more and more instances of regulatory actions among RNA molecules make evident that RNA-RNA interaction is a problem of central importance. While it is wellknown how to MFE-fold these interaction structures (Alkan et al., 2006;Huang et al., 2009) this paper constitutes progress with respect to the theoretical understanding of RNA-RNA interaction structures. Insights in the combinatorics of joint structures allows deeper understanding of analysis and design of folding algorithms as well as algorithmic approximations.
At first sight, it should be straightforward to derive the generating function of joint structures from the (eleven) recursion relations of the original rip-grammar (implied by Proposition 2) (Huang et al., 2009). While this is in principle correct, the mere statement of the generating function derived this way fills several pages. This approach is neither suitable for deriving any asymptotic formulas nor does it allow to deal with specific stacklength conditions. In fact, the extraction of its coefficients would present a nontrivial task.
We do not use the recurrences of (Huang et al., 2009) directly. Instead we build our theory of joint structures centered around the concept of shapes. The key to all results is the simple shape-grammar of Theorem 4. The basic idea here is that the collapsing of stems preserves vital information of the interaction structure. Given a shape a joint structure can be obtained via inflation, see Theorem 5.
While there exists a notion of shapes for RNA secondary structures (Giegerich et al., 2002) their combinatorics is not shape-based. Everything is organized around recurrences, which oftentimes hides deeper structural insight and connections. As a result symbolic enumeration has not been employed in order to derive the generating function of RNA secondary structures.
In contrast, RNA pseudoknot structures  represent a shape-based structure class (here further complication enters the picture as the generating function of their shapes can only be computed via the reflection principle).
The theory of joint structures presented here resembles features of the theory of modular diagrams and is in particular shape-based. However, the shapes of joint structures are governed by simple algebraic generating functions and satisfy a simple recurrence.
Let us finally outline future research. We currently study the generating function of canonical joint structures having minimum arc-length four. This derivation requires a more detailed look at shapes of joint structures since additional variables have to be introduced. The purpose of these variables is to allow to distinguish specific inflation scenarious.

Further results
In this section we generalize our results to joint structures with arc-length ≥ λ, interior stack-length ≥ σ, and exterior stack-length ≥ τ . Let T [λ] σ denote the combinatorial class of σ-canonical secondary structures having arc-length ≥ λ and T [λ] σ (n) denote the number of all σ-canonical secondary structures with n vertices having arc-length ≥ λ and Theorem 7. Let σ ∈ N, z be an indeterminant and let σ (z), the generating function of σ-canonical structures with minimum arc-length λ is given by Theorem 7 implies that T [λ] σ (z) is an algebraic function for any specified λ and σ, since F(z) is algebraic and v λ (z), u σ (z) are both rational functions.
We are now in position to establish a generalization of Theorem 5 that allows us to compute the generating function J [λ] σ,τ (x, y, z) for λ ≤ τ + 1. Let J [λ] σ,τ denote the class of joint structures with arc-length ≥ λ, interior stack-length ≥ σ, and exterior stack-length ≥ τ . Let J [λ] σ,τ (n, m, h) denote the number of joint structures in J [λ] σ,τ having n vertices in the top, m vertices in the bottom, h exterior arcs having the generating function σ,τ (x, y, z) = J [λ] σ,τ (n, m, h) x n y m z h .