Studying the virtual Euler characteristic of the moduli space of curves, Harer and Zagier compute the generating function $C_g(z)$ of unicellular maps of genus $g$. They furthermore identify coefficients, $kappa^{star}_{g}(n)$, which fully determine the series $C_g(z)$. The main result of this paper is a combinatorial interpretation of $kappa^{star}_{g}(n)$. We show that these enumerate a class of unicellular maps, which correspond $1$-to-$2^{2g}$ to a specific type of trees, referred to as O-trees. O-trees are a variant of the C-decorated trees introduced by Chapuy, F{e}ray and Fusy. We exhaustively enumerate the number $s_{g}(n)$ of shapes of genus $g$ with $n$ edges, which is a specific class of unicellular maps with vertex degree at least three. Furthermore we give combinatorial proofs for expressing the generating functions $C_g(z)$ and $S_g(z)$ for unicellular maps and shapes in terms of $kappa^{star}_{g}(n)$, respectively. We then prove a two term recursion for $kappa^{star}_{g}(n)$ and that for any fixed $g$, the sequence ${kappa_{g,t}}_{t=0}^g$ is log-concave, where $kappa^{star}_{g}(n)= kappa_{g,t}$, for $n=2g+t-1$.
In this paper we study $gamma$-structures filtered by topological genus. $gamma$-structures are a class of RNA pseudoknot structures that plays a key role in the context of polynomial time folding of RNA pseudoknot structures. A $gamma$-structure is composed by specific building blocks, that have topological genus less than or equal to $gamma$, where composition means concatenation and nesting of such blocks. Our main results are the derivation of a new bivariate generating function for $gamma$-structures via symbolic methods, the singularity analysis of the solutions and a central limit theorem for the distribution of topological genus in $gamma$-structures of given length. In our derivation specific bivariate polynomials play a central role. Their coefficients count particular motifs of fixed topological genus and they are of relevance in the context of genus recursion and novel folding algorithms.
Recently several minimum free energy (MFE) folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Their folding targets are interaction structures, that can be represented as diagrams with two backbones drawn horizontally on top of each other such that (1) intramolecular and intermolecular bonds are noncrossing and (2) there is no zig-zag configuration. This paper studies joint structures with arc-length at least four in which both, interior and exterior stack-lengths are at least two (no isolated arcs). The key idea in this paper is to consider a new type of shape, based on which joint structures can be derived via symbolic enumeration. Our results imply simple asymptotic formulas for the number of joint structures with surprisingly small exponential growth rates. They are of interest in the context of designing prediction algorithms for RNA-RNA interactions.
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.
