Combinatorics of γ -Structures

Abstract

In this article we study canonical γ-structures, a class of RNA pseudoknot structures that plays a key role in the context of polynomial time folding of RNA pseudoknot structures. A γ-structure is composed of specific building blocks that have topological genus less than or equal to γ, where composition means concatenation and nesting of such blocks. Our main result is the derivation of the generating function of γ-structures via symbolic enumeration using so called irreducible shadows. We furthermore recursively compute the generating polynomials of irreducible shadows of genus ≤ γ. The γ-structures are constructed via γ-matchings. For 1 ≤ γ ≤ 10, we compute Puiseux expansions at the unique, dominant singularities, allowing us to derive simple asymptotic formulas for the number of γ-structures.

1. Introduction and Background

An RNA sequence is a linear, oriented sequence of the nucleotides (bases) A,U,G,C. These sequences “fold” by establishing bonds between pairs of nucleotides. These bonds cannot form arbitrarily; a nucleotide can at most establish one bond, and the global conformation of an RNA molecule is determined by topological constraints encoded at the level of secondary structure, that is, by the mutual arrangements of the base pairs (Bailor et al., 2010).

Secondary structures can be interpreted as (partial) matchings in a graph of permissible base pairs (Tabaska et al., 1998). When represented as a diagram, that is, as a graph whose vertices are drawn on a horizontal line with arcs in the upper halfplane, one refers to a secondary structure with crossing arcs as a pseudoknot structure.

Folded configurations exhibit the stacking of adjacent base pairs and specific minimum arc-length conditions (Smith and Waterman, 1978), where a stack is a sequence of parallel 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} $$[(i , j) , (i + 1 , j - 1) , \ldots , (i + \tau , j - \tau) ]$$ \end{document} .

The topological classification of RNA structures (Bon et al., 2008); Andersen et al., 2013) has recently been translated into an efficient folding algorithm (Reidys et al., 2011). This algorithm a priori folds into a novel class of pseudoknot structures, the γ-structures. These γ-structures differ from pseudoknotted RNA structures of fixed topological genus of an associated fatgraph or double-line graph (Orland and Zee, 2002; Bon et al., 2008), because they have an arbitrarily high genus. They are composed of irreducible subdiagrams whose individual genus is bounded by γ and contain no bonds of length one (1-arcs; see Section 2 for details).

Nebel and Weinberg (2011) study a plethora of RNA structures. The authors study asymptotic expansions for γ = 1 and find that in the limit of large n there 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} $$j_1 \ n^ {- \frac {3} {2}} (\varrho_ {1 , 1} ^ {- 1}) ^ {n}$$ \end{document} , 1-structures, 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} $$\varrho_{1 , 1}^{- 1} = 3.8782$$ \end{document} and j₁ is some positive constant.

In this article we study canonical γ-structures, that is, partial matchings composed by irreducible motifs of genus ≤ γ without isolated arcs and 1-arcs. These motifs are called irreducible shadows. We first establish a functional relationship between the generating function of γ-matchings and that of irreducible shadows. Via this relation, we identify a polynomial P_γ(u, X), whose unique solution equals the generating function of γ-matchings. We then derive a recurrence of the generating function of irreducible shadows using the Harer-Zagier recurrence (Harer and Zagier, 1986). The generating function of γ-matchings is then expanded at its unique dominant singularity as a Puiseux-series. This implies, by means of transfer theorems (Flajolet and Sedgewick, 2009), simple asymptotic formulas for the numbers of γ-matchings.

γ-Matchings are the stepping stone to derive via Lemma 3 the further refined, bivariate generating function of γ-shapes, that is, γ-matchings containing only stacks composed by a single arc. This generating function keeps additional track of the 1-arcs, which are vital for the later inflation into γ-structures. We then compute the generating function of τ-canonical γ-structures, inflating γ-shapes by means of symbolic enumeration.

2. Some Basic Facts

2.1. γ-Diagrams

A diagram is a labeled graph over the vertex 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} $$[n ] = \{1 , \ldots , n \}$$ \end{document} , in which each vertex has degree ≤3, represented by drawing its vertices in a horizontal line. The backbone of a diagram is the sequence of consecutive integers \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} $$(1 , \ldots , n)$$ \end{document} together with the edges {{i, i + 1} ∣ 1 ≤ i ≤ n − 1}. The arcs of a diagram, (i, j), where i < j, are drawn in the upper half-plane. We shall distinguish the backbone edge {i, i + 1} from the arc (i, i + 1), which we refer to as a 1-arc.

A stack of length τ is a maximal sequence of “parallel” 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} \begin{align*}((i , j) , (i + 1 , j - 1) , \ldots , (i + \tau , j - \tau)).\end{align*} \end{document}

A stack of length ≥ τ is called a τ-canonical stack; that is, a stack of length zero is an isolated arc. The particular arc (1, n) is called a rainbow, and an arc is called maximal if it is maximal with respect to the partial order (i, j) ≤ (i′, j′) iff i′ ≤ i ∧ j ≤ j′ (Fig. 1).

FIG. 1.

(a) A diagram containing a rainbow (in boldface), three stacks ((5, 9), (6, 8)), ((10, 15), (11, 14), (12, 13)), and ((1, 19), (2, 18), (3, 17), (4, 16)). (b) The maximal arcs of a diagram displayed in (boldface).

A stack of length \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[(i , j) , (i + 1 , j - 1) , \ldots , (i + \tau , j - \tau) ]$$ \end{document} induces a sequence of pairs \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} $$[([i , i + 1 ] , [j , j - 1 ]) , ([i + 1 , i + 2 ] , [j - 1 , j - 2 ]) \ldots ([i + \tau - 1 , i + \tau ] , [j - \tau , j - \tau + 1 ]) ]$$ \end{document} . We call any of these 2τ intervals a P-interval. The interval [i + τ, j − τ] is called a σ-interval (Fig. 2).

FIG. 2.

A schematic showing σ- and P-intervals.

We shall consider diagrams as fatgraphs, \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} $${\mathbb G}$$ \end{document} ; that is, graphs G together with a collection of cyclic orderings, called fattenings, one such ordering on the half-edges incident on each vertex. Each fatgraph \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} $${\mathbb G}$$ \end{document} determines an oriented surface \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 ({\mathbb G})$$ \end{document} (Loebl and Moffatt, 2008; Penner et al., 2010), which is connected if G is and has some associated genus g(G) ≥ 0 and number r(G) ≥ 1 of boundary components. Clearly, \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 ({\mathbb G})$$ \end{document} contains G as a deformation retract (Massey, 1967). Fatgraphs were first applied to RNA secondary structures in Penner and Waterman (1993) and Penner (2004).

A diagram \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} $${\mathbb G}$$ \end{document} hence determines a unique surface \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 ({\mathbb G})$$ \end{document} (with boundary). Filling the boundary components with discs we can pass 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} $$F ({\mathbb G})$$ \end{document} to a surface without boundaries. Euler characteristic, χ, and genus, g, of this surface is given by χ = v − e + r 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} $$g = 1 - \frac {1} {2} \chi$$ \end{document} , respectively, where v, e, r is the number of discs, ribbons, and boundary components 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} $${\mathbb G}$$ \end{document} (Massey 1967). The genus of a diagram is that of its associated surface without boundary.

The shadow of a diagram of genus g is obtained by removing all noncrossing arcs, deleting all isolated vertices, and collapsing all induced stacks (i.e., maximal subsets of subsequent, parallel arcs) to single arcs (Fig. 3). We denote shadows by σ.

FIG. 3.

The shadow is obtained by removing all noncrossing arcs and isolated points and collapsing all stacks and resulting stacks into single arcs.

The shadow of a diagram \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} $${\mathbb G} , \sigma ({\mathbb G})$$ \end{document} , can possibly be empty. Furthermore, projecting into the shadow does not affect genus. Any shadow of genus g over one backbone contains at least 2g and at most (6g − 2) arcs. In particular, for fixed genus g, there exist only finitely many shadows (Reidys et al., 2011; Andersen et al., 2012). In Figure 4, we display the four shadows of genus one.

FIG. 4.

The four shadows of genus one.

A diagram is called irreducible if and only if for any two arcs, α₁, α_k contained in E, there exists a sequence 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} $$(\alpha_1 , \alpha_2 , \ldots , \alpha_{k - 1} , \alpha_k)$$ \end{document} such that (α_i, α_i₊₁) are crossing. Irreducibility is equivalent to the concept of primitivity introduced by (Bon et al., 2008), inspired by the work of Dyson (1949). According to Andersen et al. (2012), for arbitrary genus g and 2g ≤ ℓ ≤ (6g − 2), there exists an irreducible shadow of genus g having exactly ℓ arcs. We may reuse Figure 4 as an illustration of this result since the four shadows of genus one are all irreducible.

Let i_g(m) denote the number of irreducible shadows of genus g with m arcs. Since for fixed genus g there exist only finitely many shadows, we have the generating polynomial of irreducible shadows of genus g \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}_g (z) = \sum_{m = 2g}^{6g - 2} \ {\bf i}_g (m) z^m.\end{align*} \end{document}

For instance, for genus 1 and 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 I}_1 (z) = {z}^{2} \left(1 + z \right) ^{2} , \\ & {\bf I}_2 (z) = {z}^{4} \left(1 + z \right) ^{4} \left(17 + 92\ z + 96 \ {z}^{2} \right).\end{align*} \end{document}

The shadow \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} $$\sigma ({\mathbb G})$$ \end{document} of a diagram G decomposes into a set of irreducible shadows. We shall call these shadows irreducible \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} $${\mathbb G}$$ \end{document} -shadows.

Any diagram \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} $${\mathbb G}$$ \end{document} can iteratively be decomposed by first removing all noncrossing arcs as well as isolated vertices, second by collapsing any stacks, and third by removing irreducible \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} $${\mathbb G}$$ \end{document} -shadows iteratively as follows (Fig. 5):

FIG. 5.

• one removes (i.e., cuts the backbone at two points and after removal merges the cut-points) irreducible \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} $${\mathbb G}$$ \end{document} -shadows from bottom to top, such that there exists no irreducible \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} $${\mathbb G}$$ \end{document} -shadow nested within the one previously removed.

• if the removal of an irreducible \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} $${\mathbb G}$$ \end{document} -shadow induces the formation of a stack, it is collapsed into a single arc.

A diagram, \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} $${\mathbb G}$$ \end{document} , is a γ-diagram if and only if for any irreducible \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} $${\mathbb G}$$ \end{document} -shadow, \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} $${\mathbb G}^{\prime} , g ({\mathbb G}^{\prime}) \le \gamma$$ \end{document} holds.

We denote the set of τ-canonical γ-diagrams 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} $$\widetilde{{\cal G}}_{\tau , \gamma}$$ \end{document} . Such a diagram without arcs of the form (i, i + 1) (1-arcs) is called a τ-canonical γ-structure, and their set is denoted 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} $${\cal G}_{\tau , \gamma}$$ \end{document} . A γ-matching is a γ-diagram that contains only vertices of degree three. A γ-shape is a γ-matching that contains only stacks of length zero. 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 H}_{\gamma}$$ \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 S}_ \gamma$$ \end{document} denote the set of γ-matchings and γ-shapes, respectively.

2.2. Some generating functions

In this article we denote the ring of polynomials over a ring R by R[X] and the ring of formal power series ∑_n≥0 a_nXⁿ by R[[X]]. R[[X]] is a local ring with maximal ideal (X), that is, any power series with nonzero constant term is invertible. A Puiseux-series (Wall, 2004) is a power series in fractional powers of X, that is, ∑_n≥0 a_n X^n/k for some fixed \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 \in {\mathbb N}$$ \end{document} .

We denote the generating functions of a set of diagrams \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} filtered by the number of arcs D(z) = ∑_2n≥0 d(n)zⁿ. Similarly, a generating function of diagrams filtered by the length of the backbone is written as D(z) = ∑_n≥0 d(n)zⁿ. In particular, the generating functions of γ-matchings and τ canonical γ-structures 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 H}_{\gamma} (u) = \sum_{2n \ge 0}{\bf h}_ \gamma (n) u^n , \quad {\bf G}_{\tau , \gamma} (z) = \sum_{n \ge 0}{\bf g}_{\tau , \gamma} (n) z^n.\end{align*} \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} $${\cal H}_{\gamma} (n , m) \supseteq {\cal S}_{\gamma} (n , m)$$ \end{document} denote the collections of all γ-matchings and γ-shapes on 2n ≥ 0 vertices containing m ≥ 0 1-arcs with generating functions \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 H}_{\gamma} (x , y) = \sum_{m , 2n \geq 0}{\bf h}_{\gamma} (n , m) x^ny^m , \quad {\bf S}_{\gamma} (x , y) = \sum_{m , 2n \geq 0}{\bf s}_{\gamma} (n , m) x^ny^m ,\end{align*} \end{document}

where h_γ(n, m) = s_γ(n, m) = 0 if 2γ > n or if m > n.

Furthermore, there is a natural projection ϑ from γ-matchings to γ-shapes defined by collapsing each non-empty stack onto a single 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} \begin{align*}\vartheta : {\cal H}_ \gamma \to {\cal S}_ \gamma ,\end{align*} \end{document}

which is surjective and preserves irreducible shadows as well as the number of 1-arcs. ϑ restricts to a surjection \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*}\vartheta: \sqcup_{n \geq 0} {\cal H}_ \gamma (n , m) \to \sqcup_{n \geq 0} {\cal S}_ \gamma (n , m) ,\end{align*} \end{document}

which collapses each stack to an arc and preserves any irreducible shadow and also the number m of 1-arcs.

3. Combinatorics of γ-Matchings

In this section, we study γ-matchings.

Theorem 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} $$R = {\mathbb Z} [u ]$$ \end{document} . Then the following assertions hold:

(a) The generating function of γ-matchings, H_γ(u), 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} {\bf H} _ {\gamma} (u) ^ {- 1} = 1 - \left(u \ {\bf H} _ {\gamma} (u) + {\bf H} _ {\gamma} (u) ^ {- 1} \sum_ {g \le \gamma} \ {\bf I} _g \left(\frac {u {\bf H} _ {\gamma} ^ {2} (u)} {1 - u \ {\bf H} _ {\gamma} ^ {2} (u)} \right) \right) , \tag {1} \end{align} \end{document}

equivalently, \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 H} _ {\gamma} (u) - u \ {\bf H} _ {\gamma} (u) ^2 - \sum_ {g \le \gamma} \ {\bf I} _g \left(\frac {u \ {\bf H} _ {\gamma} ^ {2} (u)} {1 - u \ {\bf H} _ {\gamma} ^ {2} (u)} \right) = 1.\end{align} \end{document}

In particular, there exists a polynomial \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} $$P_ \gamma (u , X) \in R [X ]$$ \end{document} of degree (12γ − 2), whose coefficients are sums of I_g(z) coefficients, such that P_γ(u, H_γ(u)) = 0.

(b) Equation (3.1) determines H_γ(u) uniquely.

Proof. We first prove (a). Let σ be a fixed irreducible shadow of genus g having m arcs. 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 V}_ \sigma$$ \end{document} be the set of diagrams, generated by concatenating and nesting σ.

Claim 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}{\bf V}_ \sigma (u) = (1 - {\bf V}_ \sigma (u) ^{- 1} (u \ {\bf V}_ \sigma (u) ^{2}) ^m) ^{- 1}.\end{align} \end{document}

To prove Claim 1 we consider 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 V}_ \sigma$$ \end{document} -diagram. Clearly, its maximal arcs are contained in t ≥ 1 copies of σ. These arcs induce exactly (2m − 1)t σ-intervals, in each of which we find again an element 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} $${\cal V}_ \sigma$$ \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 V}_ \sigma (u) = \sum_{t \ge 0} (u^m{\bf V}_ \sigma (u) ^{2m - 1}) ^t\end{align} \end{document}

and Claim 1 follows.

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 L}_ \sigma$$ \end{document} be the set of diagrams having the fixed shape σ obtained by inflating σ-arcs into stacks, or symbolically, \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 U} \times {\rm SEQ} ({\cal U})$$ \end{document} . Here \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 U}$$ \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 R} = {\rm SEQ} ({\cal U})$$ \end{document} denote the classes of arcs and sequences of arcs. Clearly, the associated generating function 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} $${\cal U} \times {\cal R}$$ \end{document} is u(1 − u)⁻¹.

Note that each \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 L}_ \sigma$$ \end{document} -diagram contains exactly (2m − 1) σ-intervals and an arbitrary number of pairs of P-intervals. 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 F}_{\sigma}$$ \end{document} denote the set of diagrams generated by concatenating and nesting \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 L}_ \sigma$$ \end{document} -diagrams that contain no empty P-intervals. Let finally \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 W}_ \sigma$$ \end{document} be the set of one-canonical diagrams, having shapes 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 F}_ {\sigma}$$ \end{document} .

Claim 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} \begin{align} {\bf W} _ \sigma (u) ^ {- 1} = 1 - {\bf W} _ \sigma (u) ^ {- 1} \left(\frac {\frac {u} {1 - u} \ {\bf W} _ \sigma^2 (u)} {1 - \frac {u} {1 - u} \ ({\bf W} _ \sigma^2 (u) - 1)} \right)^ {m} . \tag {2} \end{align} \end{document}

We shall construct \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 W}_ \sigma$$ \end{document} using 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 U}$$ \end{document} ; sequences 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} ; induced 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 N}$$ \end{document} ; and sequence of induced 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 M}$$ \end{document} . The 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 F}_{\sigma}$$ \end{document} is obtained by concatenating and nesting \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 L}_ \sigma$$ \end{document} -diagrams that do not contain any empty P-intervals (Fig. 6).

FIG. 6.
First, a fixed irreducible shadow σ is inflated into 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 L}_ \sigma$$ \end{document} -diagram; second, we pass 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} $${\cal F}_ {\sigma}$$ \end{document} -diagram by inserting a nontrivial \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 L}_ \sigma$$ \end{document} -diagram in one of the P-intervals.

An induced arc, that is, an arc together with at least one nontrivial \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 F}_{ \sigma}$$ \end{document} -diagram in either one or in both P-intervals \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 U} \times (({\cal F}_ {\sigma} - 1) + ({\cal F}_ {\sigma} - 1) + ({\cal F}_ {\sigma} - 1) ^2 )\, =\, {\cal U} \times ({\cal F}_ \sigma^2 - 1 ).\end{align} \end{document}

Clearly, we have for a single induced arc N(u) = u(F_σ(u)² − 1) and for a sequence of induced 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 M} = {\rm SEQ} ({\cal N})$$ \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} \begin{align} {\bf M} (u) = \frac {1} {1 - u \left({\bf F} _ \sigma (u) ^2 - 1 \right)} .\end{align} \end{document}

By construction, the maximal arcs 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} $${\cal F}_{\sigma}$$ \end{document} -diagram coincide with those of its underlying \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 V}_ \sigma$$ \end{document} -diagram. Therefore, \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 F}_{\sigma} = \sum_{t \geq 0} (({\cal U} \times {\cal M}) ^m \ {\cal F}_ \sigma^{2m - 1}) ^t\end{align} \end{document}

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 F} _ \sigma (u) = \sum_ {t \geq 0} \left(\left(\frac {u} {1 - u ({\bf F} _ \sigma (u) ^2 - 1)} \right) ^m \ {\bf F} _ \sigma (u) ^ {2m - 1} \right)^t. \tag {3} \end{align} \end{document}

Next we inflate the arcs 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} $${\cal F}_ \sigma$$ \end{document} -diagram into 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 U} \times {\cal R}$$ \end{document} .

This inflation process generates \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 W}_ \sigma$$ \end{document} -diagrams, and 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} $${\cal W}_ \sigma$$ \end{document} -diagram can be constructed from a unique fixed irreducible shadow σ of genus g with m arcs. 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 W} _ \sigma (u) = \sum_ {t \geq 0} \left(\left(\frac {\frac {u} {1 - u}} {1 - \frac {u} {1 - u} ({\bf W} _ \sigma (u) ^2 - 1)} \right)^m \ {\bf W} _ \sigma (u) ^ {2m - 1} \right)^t , \tag {4} \end{align} \end{document}

whence Claim 2.

Claim 3

Let M be the set of irreducible shadows of genus g ≤ γ. 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} {\bf W} _M (u) ^ {- 1} = 1 - \sum_ {g \leq \gamma} \sum_ {1 < m} {{\bf i} _g (m) \ \bf W} _M (u) ^ {- 1} \left(\frac {u \ {\bf W} _M^2 (u)} {1 - u \ {\bf W} _M^2 (u)} \right)^m. \tag {5} \end{align} \end{document}

The maximal arcs of 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 V}_M$$ \end{document} -structure, partition into the maximal arcs of t concatenated irreducible shadows \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} $$\sigma_1 , \ldots , \sigma_t$$ \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}\sum_{\{ \sigma_{1} , \ldots , \sigma_{t} \} \atop \sigma_{i} \in M} 1 = \left(\sum_{g \leq \gamma} \sum_{1 < m}{\bf i}_g (m) \right)^t. \tag{6}\end{align} \end{document}

These maximal arcs induce exactly (2m − 1)t σ-intervals. In each σ-interval, we find again an element 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} $${\cal V}_M$$ \end{document} . Thus for any σ_i having m arcs, 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} $${\cal V}_M^{2m - 1}$$ \end{document} , which leads to the term u^mV_M(u)^2m−1. It remains to sum over all t, that is, expressing all the decompositions 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} $${\cal V}_{M_ \gamma}$$ \end{document} -structures into concatenated, irreducible shadows, and we obtain \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 V}_M (u) = \sum_{t \ge 0} \left(\sum_{g \leq \gamma} \sum_{m > 1} {\bf i}_g (m) u^m{\bf V}_M (u) ^{2m - 1} \right) ^t. \tag{7}\end{align} \end{document}

The passage 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} $${\cal V}_M$$ \end{document} 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 L}_M$$ \end{document} , as well as that 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} $${\cal L}_M$$ \end{document} 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 F}_M$$ \end{document} , follows from Claim 2, 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 F} _M (u) = \sum_ {t \geq 0} \left(\sum_ {g \leq \gamma} \sum_ {m > 1} {{\bf i} _g (m) \ \bf F} _M (u) ^ {- 1} \left(\frac {u \ {\bf F} _M^2 (u)} {1 - u ({\bf F} _M^2 (u) - 1)} \right)^m \right)^t. \tag {8} \end{align} \end{document}

Here F_M(u)⁻¹ exists 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} $${\mathbb C} [[u ] ]$$ \end{document} , having a nonzero constant term. Next we inflate the arcs 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} $${\cal F}_M$$ \end{document} -structure into stacks, obtaining \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 W} _M (u) ^ {- 1} = 1 - \sum_ {g \leq \gamma} \sum_ {1 < m} {{\bf i} _g (m) \ \bf W} _M (u) ^ {- 1} \left(\frac {u \ {\bf W} _M^2 (u)} {1 - u \ ({\bf W} _M^2 (u))} \right)^m. \tag {9} \end{align} \end{document}

We next derive the functional equation for H_γ(u) by incorporating noncrossing arcs. Since the maximal arcs composed of noncrossing arcs are exactly rainbows, the generating function 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} $${\cal H}_{\gamma}$$ \end{document} -diagrams nested in a rainbow is given by uH_γ(u). As in Claim 3, we 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}{\bf H}_{\gamma} (u) ^{- 1} = 1 - \sum_{g \leq \gamma} \left(u \ {\bf H}_{\gamma} (u) + {\bf H}_{\gamma} (u) ^{- 1} \ \sum_{m > 1} {\bf i}_g (m) \ \vartheta (u) ^m \right) ,\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} \begin{align}\vartheta (u) = \frac {u \ {\bf H} _ {\gamma} ^ {2} (u)} {1 - u \ {\bf H} _ {\gamma} ^ {2} (u)} .\end{align} \end{document}

Setting w_u(X) = 1 − uX², Equation 1 gives rise to the polynomial \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}P_ \gamma (u , X) = w_u (X) ^ {\kappa_ \gamma} (- 1 + X - u \ X^2) - \sum_ {g \leq \gamma} \ w_u (X) ^ {\kappa_ \gamma} \ {\bf I} _g \left(\frac {u \ X^ {2}} {w_u (X)} \right) , \tag {10} \end{align} \end{document}

where κ_γ = 6γ − 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} $${\rm deg} (P_ \gamma (u , X)) = (2 + 2 \kappa_ \gamma)$$ \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} $$\left[X^{2 + 2 \kappa_ \gamma} \right] P_ \gamma (u , X) = - u^{1 + \kappa_ \gamma}$$ \end{document} , and P_γ(u, H_γ(u)) = 0, whence (a).

It remains to prove (b). Since M is the finite set of irreducible shadows of genus g ≤ γ, and any such shadow has 2g ≤ m ≤ κ_γ arcs (Andersen et al., 2012), any M-shadow has ≤ κ_γ arcs. 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} $$v (u) = 1- u \ {\bf H}_{\gamma}^{2} (u)$$ \end{document} , Equation 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}v (u) ^ {\kappa_ \gamma} = {\bf H} _ {\gamma} (u) v (u) ^ {\kappa_ \gamma} - u \ {\bf H} ^2_ {\gamma} (u) \ v (u) ^ {\kappa_ \gamma} - \sum_ {g \leq \gamma} \ v (u) ^ {\kappa_ \gamma} \ {\bf I} _g \left(\frac {u \ {\bf H} _ {\gamma} ^ {2} (u)} {v (u)} \right)\end{align} \end{document}

and consequently \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 H} _ {\gamma} (u) & = - {\bf H} _ {\gamma} (u) \sum_ {i = 1} ^ {\kappa_ \gamma} \ {\kappa_ \gamma \choose i} 1^ {\kappa_ \gamma - i} {(v (u) - 1) ^i} + u \ {\bf H} ^2_ {\gamma} (u) \ v (u) ^ {\kappa_ \gamma} + v (u) ^ {\kappa_ \gamma} & (11) \\ & \quad+ \sum_ {g \leq \gamma} \ v (u) ^ {\kappa_ \gamma} {\bf I} _g \left(\frac {u \ {\bf H} _ {\gamma} ^ {2} (u)} {v (u)} \right). \end{align} \end{document}

All coefficients of H_γ(u) in the RHS of Equation 11, are polynomials in u of degree ≥ 1, whence any [zⁿ]H_γ(u) for n ≥ (κ_γ + 1) can be recursively computed. Accordingly, Equation 11 determines H_γ(u) uniquely. ■

4. Irreducible Shadows

The bivariate generating function of irreducible shadows of genus g with m arcs is denoted 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 I} (z , t) = \sum_{g \geq 1}{\bf I}_g (z) \ t^g = \sum_{g \geq 1} \sum_{m = 2g}^{6g - 2} \ {\bf i}_g (m) \ z^m t^g.\end{align} \end{document}

Let c_g(m) denote the number of matchings of genus g with m arcs. We have the generating function of matchings of genus g \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}_g (z) = \sum_{m \geq 2g} \ {\bf c}_g (m) z^m.\end{align} \end{document}

The bivariate generating function of matchings of genus g with m arcs is denoted 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 , t) = \sum_{g \geq 0}{\bf C}_g (z) \ t^g = \sum_{g \geq 0} \sum_{m \geq 2g} \ {\bf c}_g (m) \ z^m t^g.\end{align} \end{document}

Theorem 2

The generating functions C(z, t) and I(z, t) 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 C} (z , t) ^ {- 1} = 1 - \left(z \ {\bf C} (z , t) + {\bf C} (z , t) ^ {- 1} {\bf I} \left(\frac {z \ {\bf C} (z , t) ^2} {1 - z \ {\bf C} (z , t) ^2} , t \right) \right) ,\end{align} \end{document}

equivalently, \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 , t) - z \ {\bf C} (z , t) ^2 - {\bf I} \left(\frac {z \ {\bf C} (z , t) ^2} {1 - z \ {\bf C} (z , t) ^2} , t \right) = 1. \tag {12} \end{align}\end{document}

Proof. We distinguish the classes of blocks into two categories characterized by the unique component containing all maximal arcs (maximal component). Namely, ■

• blocks whose maximal component contains only one arc,

• blocks whose maximal component is an irreducible (nonempty) matching.

In the first case, the removal of the maximal component (one arc) generates again an arbitrary matching, which translates into the term \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 \ {\bf C} (z , t).\end{align} \end{document}

Let T(z, t) denote the (genus-filtered) generating function of blocks of the second type. The decomposition of matchings into a sequence of blocks 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}{\bf C} (z , t) ^{- 1} = 1 - \left(z \ {\bf C} (z , t) + {\bf T} (z , t) \right).\end{align} \end{document}

Let σ be a fixed irreducible shadow of genus g having n arcs. Let T_σ(z, t) be the generating function of blocks, having σ as the shadow of its unique maximal component. 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}{\bf T} (z , t) = \sum_{\sigma \in {\cal J}}{\bf T}_ \sigma (z , t) ,\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 J}$$ \end{document} denotes the set of irreducible shadows.

We shall construct \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}_ \sigma$$ \end{document} in three steps using 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} ; sequences 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 K}$$ \end{document} ; induced 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 N}$$ \end{document} ; sequence of induced 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 M}$$ \end{document} ; and arbitrary matchings, \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} .

Step I: We inflate each arc in σ into a sequence of induced arcs (Fig. 7). An induced arc, that is an arc together with at least one nontrivial match in either one or in both P-intervals \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 (({\cal C} - 1) + ({\cal C} - 1) + ({\cal C} - 1) ^2 ) = {\cal R} \times ({\cal C}^2 - 1 ).\end{align} \end{document}

FIG. 7.
Step I: Inflation of each arc in σ into a sequence of induced arcs.

Clearly, we have for a single induced arc N(z, t) = z (C(z, t)² − 1), guaranteed by the additivity of genus, and for a sequence of induced 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 M} = {\rm SEQ} ({\cal N})$$ \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} \begin{align} {\bf M} (z , t) = \frac {1} {1 - z \left({\bf C} (z , t) ^2 - 1 \right)} .\end{align} \end{document}

Inflating each arc into a sequence of induced 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} $$R^n \times {\cal M}^n$$ \end{document} , gives the corresponding 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}z^n {\bf M} (z , t) ^n = \left(\frac {z} {1 - z \left({\bf C} (z , t) ^2 - 1 \right)} \right)^n ,\end{align} \end{document}

since the genus is additive.

Step II: We inflate each arc in the component with shadow σ into stacks (Fig. 8). The corresponding generating function is \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}\left(\frac {\frac {z} {1 - z}} {1 - \frac {z} {1 - z} \left({\bf C} (z , t) ^2 - 1 \right)} \right)^n = \left(\frac {z} {1 - z {\bf C} (z , t) ^2} \right)^n\end{align} \end{document}

FIG. 8.
Step II: Inflation of each arc in the component with shadow σ into stacks.

Step III: We insert additional matchings at exactly (2n − 1) σ-intervals (Fig. 9). Accordingly, the generating function is C(z, t)²ⁿ⁻¹.

FIG. 9.
Step III: Insertion of additional matchings at exactly (2n − 1) σ-intervals.

Combining these three steps and utilizing additivity of the genus, we arrive 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 T} _ \sigma (z , t) & = t^g \left(\frac {z} {1 - z {\bf C} (z , t) ^2} \right)^n {\bf C} (z , t) ^ {2n - 1} \\ & = t^g {\bf C} (z , t) ^ {- 1} \ \left(\frac {z {\bf C} (z , t) ^2} {1 - z {\bf C} (z , t) ^2} \right)^n. \end{align} \end{document}

Therefore \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 T} (z , t) & = \sum_ {\sigma \in {\cal J}} {\bf T} _ \sigma (z , t) \\ & = \sum_ {g , n} {\bf i} _g (n) t^g \ {\bf C} (z , t) ^ {- 1} \ \left(\frac {z \ {\bf C} (z , t) ^2} {1 - z {\bf C} (z , t) ^2} \right) ^n. \end{align} \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 T} (z , t) = {\bf C} (z , t) ^ {- 1} {\bf I} \left(\frac {z \ {\bf C} (z , t) ^2} {1 - z \ {\bf C} (z , t) ^2} , t \right) ,\end{align} \end{document}

completing the proof of Equation 12. ■

Now we can derive a recursion for I_g(z) from Theorem 2.

Corollary 1

For g ≥ 1, I_g(z) satisfies the following 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} {\bf I} _g (z) =& {\bf C} _g (\theta (z)) - \theta (z) \ \sum_ {i = 0} ^g {\bf C} _i (\theta (z)) {\bf C} _ {g - i} (\theta (z)) \\ & - \sum_ {j = 1} ^ {g - 1} [t^ {g - j} ] {\bf I} _j \left(\frac {\theta (z) \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (\theta (z)) t^k) ^2} {1 - \theta (z) \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (\theta (z)) t^k) ^2} \right) , \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}$$\theta (z) = \frac {z(z + 1)} {(2z + 1)^2}$$\end{document} .

Proof. We compute the coefficient of t^g on both sides of Equation 12 \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} [t^g ] {\bf C} (t , z) - z \ [t^g ] {\bf C} (t , z) ^2 - [t^g ] {\bf I} \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} , t \right) = 0\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 C} _g (z) - z \ \sum_ {i = 0} ^g {\bf C} _i (z) {\bf C} _ {g - i} (z) - \sum_ {j = 1} ^ {g} [t^ {g - j} ] {\bf I} _j \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} \right) = 0\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 C} _g (z) - z \ \sum_ {i = 0} ^g {\bf C} _i (z) {\bf C} _ {g - i} (z) - \sum_ {j = 1} ^ {g - 1} [t^ {g - j} ] {\bf I} _j \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} \right) \\ & = [t^ {0} ] {\bf I} _g \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} \right) \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}[t^ {g - j} ] {\bf I} _j \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} \right) = [t^ {g - j} ] {\bf I} _j \left(\frac {z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} {1 - z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} \right).\end{align} \end{document}

Note 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}[t^ {g - j} ] {\bf I} _j \left(\frac {z \ {\bf C} (t , z) ^2} {1 - z \ {\bf C} (t , z) ^2} \right) = [t^ {g - j} ] {\bf I} _j \left(\frac {z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} {1 - z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} \right).\end{align} \end{document}

Hence, \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} \openup-2pt\begin{align} & {\bf C} _g (z) - z \ \sum_ {i = 0} ^g {\bf C} _i (z) {\bf C} _ {g - i} (z) - \sum_ {j = 1} ^ {g - 1} [t^ {g - j} ] {\bf I} _j \left(\frac {z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} {1 - z \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (z) t^k) ^2} \right) \\ & = {\bf I} _g \left(\frac {z \ {\bf C} _0 (z) ^2} {1 - z \ {\bf C} _0 (z) ^2} \right) \end{align} \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} $$\theta (z) = \frac {z (z + 1)} {(2z + 1) ^2}$$ \end{document} , 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} $$z = \theta (y) = \frac {y (y + 1)} {(2y + 1) ^2}$$ \end{document} . Then 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} \openup-2pt\begin{align} {\bf I} _g (y) = & {\bf C} _g (\theta (y)) - \theta (y) \ \sum_ {i = 0} ^g {\bf C} _i (\theta (y)) {\bf C} _ {g - i} (\theta (y)) \\ &- \sum_ {j = 1} ^ {g - 1} [t^ {g - j} ] {\bf I} _j \left(\frac {\theta (y) \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (\theta (y)) t^k) ^2} {1 - \theta (y) \ (\sum_ {k = 0} ^ {g - j} {\bf C} _k (\theta (y)) t^k) ^2} \right) \end{align} \end{document}

completing the proof. ■

A seminal result (Harer and Zagier 1986), computes a recursion and generating function for the number c_g(m) as follows:

Lemma 1

(Harer and Zagier 1986) The c_g(m) satisfy 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) \ {\bf c}_g (m) = 2 (2m - 1) \ {\bf c}_g (m - 1) + (2m - 1) (m - 1) (2m - 3) \ {\bf c}_{g - 1} (m - 2) , \tag{13}\end{align} \end{document}

where c_g(m) = 0 for 2g > m.

The recursion Equation 13 is equivalent to the ODE \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 (1 - 4z) \frac {d} {dz} {\bf C} _g (z) + (1 - 2z) {\bf C} _g (z) = \Phi_ {g - 1} (z) \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} \begin{align} & \Phi_ {g - 1} (z) = z^2 \left(4z^3 \frac {d^3} {dz^3} {\bf C} _ {g - 1} (z) + 24 z^2 \frac {d^2} {dz^2} {\bf C} _ {g - 1} (z) + 27z \frac {d} {dz} {\bf C} _ {g - 1} (z) + 3 {\bf C} _ {g - 1} (z) \right) \end{align} \end{document}

with initial condition C_g(0) = 0 since r = n + 1 − 2g has no positive solution r > 0 for n < 2g. Therefore, we can recursively compute C_g(z) by solving Equation (14) via Maple.

Theorem 3

(Andersen et al., 2013) For any g ≥ 1 the generating function C_g(z) 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} _g (z) = Q_g (z) \frac {\sqrt {1 - 4 \ z}} {(1 - 4z) ^ {3g}} , \tag {15} \end{align} \end{document}

where Q_g(z) is a polynomial with integral coefficients of degree at most (3g − 1), Q_g(1/4) ≠ 0, [z^2g]Q _g(z)≠ 0 and [z^h]Q_g(z) = 0 for 0 ≤ h ≤ 2g − 1.

The recursion Equation (14) permits the calculation of the polynomials Q_g(z), the first five of which are given as follows (Andersen et al., 2013): \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}Q_1 (z) & = z^2 , \\ Q_2 (z) & = 21z^4 \ \left(z + 1 \right) \\ Q_3 (z) & = 11z^6 \ \left(158 \ {z}^{2} + 558 \ z + 135 \right) , \\ Q_4 (z) & = 143z^8 \left(2339 \ {z}^{3} + 18378 \ {z}^{2} + 13689 \ z + 1575 \right) , \\ Q_5 (z) & = 88179z^{10} \ \left(1354 \ {z}^{4} + 18908 \ {z}^{3} + 28764 \ {z}^{2} + 9660 \ z + 675 \right).\end{align} \end{document}

Applying Corollary 1 together with the generating function C_g(z), we recursively compute I_g(z).

For example, for g = 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}{\bf I}_1 (z) & = {\bf C}_1 (\theta (z)) - 2 \theta (z) \ {\bf C}_0 (\theta (z)) {\bf C}_{1} (\theta (z)) \\ & = {z}^{2} \left(1 + z \right) ^{2}.\end{align} \end{document}

For 1 ≤ g ≤ 8, we list I_g(z) 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 I}_1 (z) = & {z}^{2} (1 + z) ^{2} , \\ {\bf I}_2 (z) = & {z}^{4} (1 + z) ^{4} (17 + 92 \ z + 96 \ {z}^{2}) \\ {\bf I}_3 (z) = & {z}^{6} (1 + z) ^{6} (1259 + 15928 \ z + 61850 \ {z}^{2} + 92736 \ {z}^{3} + 47040 \ {z}^{4}) \\ {\bf I}_4 (z) = & {z}^{8} (1 + z) ^{8} (200589 + 4245684 \ z + 31264164 \ {z}^{2} + 107622740 \ {z}^{3} \\ & + 188262816 \ {z}^{4} + 161967360 \ {z}^{5} + 54333440 \ {z}^{6}) \\ {\bf I}_5 (z) = & {z}^{10} (1 + z) ^{10} (54766516 + 1681752448 \ z + 19092044658 \ {z}^{2} \\ & + 109184482584 \ {z}^{3} + 353376676011 \ {z}^{4}) \\ & + 675135053568 \ {z}^{5} + 753610999040 \ {z}^{6} \\ & + 453941596160 \ {z}^{7} + 113867919360 \ {z}^{8}) \\ {\bf I}_6 (z) = & 3 \ {z}^{12} (1 + z) ^{12} (7613067765 + 312905543772 \ z + 4932317894440 \ {z}^{2} \\ & + 40797413383380 \ {z}^{3} + 200964285178270 \ {z}^{4} + 626595744773516 \ {z}^{5} \\ & + 1268150755326432 \ {z}^{6} + 1660845652501760 \ {z}^{7} + 1357241056522240 \ {z}^{8} \\ & + 628740761518080 \ {z}^{9} + 126004558299136 \ {z}^{10}) \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}_7 (z) = & {z}^{14} (1 + z) ^{14} (13532959408258 + 706557271551408 \ z \\ & + 14506513039164060 \ {z}^{2} + 160434554727348896 \ {z}^{3} \\ & + 1089075339931680039 \ {z}^{4} + 4857650169218369856 \ {z}^{5} \\ & + 14771712773087154704 \ {z}^{6} + 31138771188689736192 \ {z}^{7} \\ & + 45486763075779571200 \ {z}^{8} + 45167296685229793280 \ {z}^{9} \\ & + 29078583024627105792 \ {z}^{10} \\ & + 10941912454886326272 \ {z}^{11} + 1826131581135486976 \ {z}^{12}) \\ {\bf I}_8 (z) =& {z}^{16} (1 + z) ^{16} (10826939105517381 + 692156096364848676 \ z \\ & + 17724869034206737356 \ {z}^{2} \\ & + 249069951630509297956 \ {z}^{3} + 2192230050291936695620 \ {z}^{4} \\ & + 12980362620620450943588 \ {z}^{5} + 53923920139564145104556 \ {z}^{6} \\ & + 161060520394034807160164 \ {z}^{7} + 349969438514715552162336 \ {z}^{8} \\ & + 553647075623879302120960 \ {z}^{9} + 630641488385967162351616 \ {z}^{10} \\ & + 503519879227179011162112 \ {z}^{11} + 267275771110990512783360 \ {z}^{12} \\ & + 84670509266097640833024 \ {z}^{13} + 12107536630199227514880 \ {z}^{14}) \end{align} \end{document}

We conjecture that the polynomial I_g(z), for arbitrary g, has z^2g (1 + z)^2g as a factor.

5. Asymptotics of γ-Matchings

Let us begin recalling the following result of Flajolet and Sedgewick (2009):

Theorem 4

Let y(u) = ∑_n≥0y_nuⁿ be a generating function, analytic at 0, satisfying a polynomial equation Φ(u, y) = 0. Let ρ be the real dominant singularity of y(u). Define the resultant of Φ(u, y) 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} $$\frac {\partial} {\partial y} \Phi (u , y)$$ \end{document} as polynomial in y \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}\Delta (u) = {\bf R} \left(\Phi (u , y) , \frac {\partial} {\partial y} \Phi (u , y) , y \right).\end{align} \end{document}

(1) The dominant singularity ρ is unique and a root of the resultant Δ(u) and there exists π = y(ρ), satisfying the system of equations, \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 (\rho , \pi) = 0 , \quad \Phi_y (\rho , \pi) = 0. \tag{16}\end{align} \end{document}

(2) If Φ(u, y) satisfies the conditions: \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_u (\rho , \pi) \neq 0 , \quad \Phi_{y y} (\rho , \pi) \neq 0 , \tag{17}\end{align} \end{document}

then y(u) has the following expansion 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}y (u) = \pi + \lambda (\rho - u) ^ {\frac {1} {2}} + O (\rho - u) ,\end{align} \end{document}

for some nonzero constant λ

Further the coefficients of y(u) 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}[u^n ] y (u) \,\sim \,c \ n^ {- \frac {3} {2}} \rho^ {- n} , \quad n \rightarrow \infty ,\end{align} \end{document}

for some constant c > 0.

Proof. The proof of (1) can be found in Flajolet and Sedgewick (2009) or Hille (1962, pp. 103). To prove (2), let Ψ(u, y) = Φ(ρ − u, π − y). Immediately, we have Ψ(0, 0) = 0. Puiseux's theorem (Wall, 2004) guarantees a solution of y − π in terms of a Puiseux series in ρ − u. Note that Equations (16) and (17) are equivalent 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} \begin{align}\Psi (0 , 0) = 0 , \quad \Psi_y (0 , 0) = 0 , \quad \Psi_u (0 , 0) \neq 0 , \quad \Psi_{y y} (0 , 0) \neq 0.\end{align} \end{document}

Then we apply Newton's polygon method to determine the type of expansion and find the first exponent of u to be \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 {1} {2}$$ \end{document} . Therefore, the Puiseux series expansion of y(u) has the required form. The asymptotics of the coefficients follow from Equation (18) as a straightforward application of the transfer theorem (Flajolet and Sedgewick, 2009, pp. 389, Theorem VI.3). ■

Combining Theorem 1 and Theorem 4, the asymptotic analysis of H_γ(u) follows.

Theorem 5

For 1 ≤ γ ≤ 10, 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}\Delta_ \gamma (u) = {\bf R} \left(P_ \gamma (u , X) , \frac {\partial} {\partial X} P_ \gamma (u , X) , X \right)\end{align} \end{document}

the resultant of P_γ(u, X) 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} $$\frac {\partial} {\partial X} P_ \gamma (u , X)$$ \end{document} as polynomials in X, and ρ_γ denote the real dominant singularity of H_γ(u).

(a) The dominant singularity ρ_γ is unique and a root of Δ_γ(u),

(b) at ρ_γ 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} $${\bf H} _ {\gamma} (u) = \pi_ \gamma + \lambda_ \gamma (\rho_ {\gamma} - u) ^ {\frac {1} {2}} + O (\rho_ {\gamma} - u)$$ \end{document} , for some nonzero constant λ_γ.

(c) the coefficients of H_γ(u) are 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}[u^n ] {\bf H}_{\gamma} (u) \,\sim \,c_ \gamma \ n^{- 3 / 2} \ \rho_{\gamma}^{- n}\end{align} \end{document}

for some c_γ > 0.

Proof. Pringsheim's theorem (Flajolet and Sedgewick, 2009), pp. 240) guarantees that for any γ, H_γ(u) has a dominant real singularity ρ_γ > 0. To prove the singular expansion of the function and asymptotic of the coefficients, we verify P_γ(u, X), for 1 ≤ γ ≤ 10, satisfy the condition of Theorem 4, and the results follow. ■

6. Combinatorics of γ-Diagrams

Lemma 2

For any γ ≥ 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 S} _ \gamma (u , e) = \frac {1 + u} {1 + 2u - ue} {\bf H} _ \gamma \left(\frac {u (1 + u)} {(1 + 2u - ue) ^2} \right) . \tag {19} \end{align} \end{document}

The proof of Lemma 2 can be obtained by standard symbolic method.

Lemma 3

Let λ be a fixed γ-shape with s ≥ 1-arcs and m ≥ 0 1-arcs. Then the generating function of τ-canonical γ-diagrams containing no 1-arcs that have shape λ 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} ^ {\lambda} _ {\tau , \gamma} (z) = (1 - z) ^ {- 1} \left(\frac {z^ {2 \tau}} {(1 - z^2) (1 - z) ^2 - (2z - z^2) z^ {2 \tau}} \right)^s \ z^m.\end{align} \end{document}

In particular, \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}^ \lambda_{\tau , \gamma} (z)$$ \end{document} depends only upon the number of arcs and 1-arcs in λ.

Our main result about enumerating τ-canonical γ-structures follows.

Theorem 6

Suppose γ, τ ≥ 1 and 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} $$u_ \tau (z) = \frac {(z^2) ^ {\tau - 1}} {z^ {2 \tau} - z^2 + 1}$$ \end{document} . Then the generating function G_τ,γ(z) is algebraic and 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} _ {\tau , \gamma} (z) = \frac {1} {u_ \tau (z) z^2 - z + 1} \ {\bf H} _ \gamma \left(\frac {u_ \tau (z) z^2} {\left(u_ \tau (z) z^ {2} - z + 1 \right) ^2} \right). \tag {20} \end{align} \end{document}

In particular for 1 ≤ s, i ≤ 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}[z^n ] {\bf G} _ {s , i} (z)\, \sim\, k_ {s , i} \ n^ {- \frac {3} {2}} (\rho_ {s , i} ^ {- 1}) ^n ,\end{align} \end{document}

for some constants k_s_,i > 0, 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} $$\rho_{s , i}^{- 1}$$ \end{document} , we have Table 1.

Table 1.
The Exponential 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} $$\rho^{- 1}_{s , i}$$ \end{document} , for 1 ≤ s, i ≤ 2

(s, i) (1, 1) (2, 1) (1, 2) (2, 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} $$\rho^{- 1}_{s , i}$$ \end{document} 3.6005 2.2759 3.8846 2.3553

Proof. Since each γ-diagram has a unique γ-shape, λ, having some number m ≥ 0 of 1-arcs, 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}_{\tau , \gamma} (z) = \sum_{m \geq 0} \sum_{\lambda \ \gamma - {\rm shape} \atop {\rm having} \ m \ 1 - {\rm arcs}} {\bf G}^ \lambda_{\tau , \gamma} (z) . \tag{21}\end{align} \end{document}

According to Lemma 3, \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}^ \lambda_{\tau , \gamma} (z)$$ \end{document} only depends on the number of arcs and 1-arcs of λ, and we can therefore express \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}_{\tau , \gamma} (z) & = {1 \over{z - 1}} {\bf S}_ \gamma \left({{z^{2 \tau}} \over{(1 - z^2) (1 - z) ^2 - (2z - z^2) z^{2 \tau}}} , z \right). \\ & = {1 \over (1 - z) + {u_ \tau (z)}z^2} \ {\bf H}_ \gamma \left({{z^2 \ {u_ \tau (z)}} \over {\left ((1 - z) + {u_ \tau (z)}z^2 \right) ^2}} \right) ,\end{align} \end{document}

using Lemma 2 in order to confirm Equation 23, where the second equality follows from direct computation. 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}\theta_ \tau (z) = \frac {z^2 \ {u_ \tau (z)}} {\left((1 - z) + {u_ \tau (z)} z^2 \right) ^2} \end{align} \end{document}

denote the argument of H_γ in this expression. 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} $$\theta (z) \in {\mathbb C} (z)$$ \end{document} . Since θ_σ(0) = 0 the composition H_γ(θ(z)) is well defined as a power series. Obviously, P_γ(z, H_γ(z)) = 0 guarantees P_γ(θ_τ(z), H_γ(θ_τ(z)) = 0. We have the following Hasse diagram of fields:

from which we immediately conclude that G_τ,γ(z) is algebraic. Pringsheim's theorem (Flajolet and Sedgewick, 2009) guarantees that for any γ, τ ≥ 1, G_τ_,γ(z) has a dominant real singularity ρ_τ_,γ > 0.

According to Theorem 5 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 H}_i (z) = \pi_1 + \sum_{j \ge 1} a_{j , i} \left(\left(\mu_i - z \right) ^{1 / 2} \right)^{j} \quad {\rm and} \quad [z^n ] {\bf H}_i (z) \,\sim \,k_i \ n^{- 3 / 2} \ \left(\mu_i^{- 1} \right) ^n.\end{align} \end{document}

For τ = 1, 2, we verify directly that ρ_1,i and ρ_2,i are the unique solutions of minimum modulus of θ₁(z) = μ_i and θ₂(z) = μ_i. These solutions are strictly smaller than any other singularities of θ₁(z) and θ₂(z) and furthermore 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} $$\theta_1^{\prime} (\rho_{1 , i}) \neq 0$$ \end{document} as well 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} $$\theta_2^{\prime} (\rho_{2 , i}) \neq 0$$ \end{document} . It follows that G_1,i(z) and G_2,i(z) are governed by the supercritical paradigm (Flajolet and Sedgewick, 2009), which in turn 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}[z^n ] {\bf G}_{s , i} (z) \,\sim \,k_{s , i} \ n^{- 3 / 2} \left(\rho_{s , i}^{- 1} \right) ^n , \tag{22}\end{align} \end{document}

where s = 1, 2 and k_s_,i is some positive constant. ■

Theorem 6 has its analogue for τ-canonical, γ-diagrams containing 1-arcs. The asymptotic formula in case of τ = 1, γ = 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}[z^n ] \widetilde {{\bf G}} _ {1 , 1} (z) \,\sim \,j_1 \ n^ {- \frac {3} {2}} (\varrho_ {1 , 1} ^ {- 1}) ^ {n} \end{align} \end{document}

is due to Nebel and Weinberg (2011), who used the explicit grammar developed in Reidys et al. (2011) to obtain an algebraic equation 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} $$\widetilde{{\bf G}}_{1 , 1} (z)$$ \end{document} .

Corollary 2

Suppose γ, τ ≥ 1 and 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} $$u_ \tau (z) = \frac {(z^2) ^ {\tau - 1}} {z^ {2 \tau} - z^2 + 1}$$ \end{document} . Then the generating function of τ-canonical γ-diagrams containing 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} $$\widetilde{{\bf G}}_{\tau , \gamma} (z)$$ \end{document} , is algebraic 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}\widetilde {{\bf G}} _ {\tau , \gamma} (z) = {\bf H} _ \gamma \left(\frac {u_ \tau (z) z^2} {(1 - z) ^2} \right). \tag {23} \end{align} \end{document}

In particular for γ = 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}[z^n ] \widetilde {{\bf G}} _ {1 , 1} (z) \,\sim \,j_1 \ n^ {- \frac {3} {2}} (\varrho_ {1 , 1} ^ {- 1}) ^ {n} , \quad {\rm and} \quad [z^n ] \widetilde {{\bf G}} _ {2 , 1} (z) \,\sim \,j_2 \ n^ {- \frac {3} {2}} (\varrho_ {2 , 1} ^ {- 1}) ^ {n} \end{align} \end{document}

for some constants j₁, j₂, 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} $$\varrho_{1 , 1}^{- 1} = 3.8782$$ \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} $$\varrho_{2 , 1}^{- 1} = 2.3361$$ \end{document} .

Proof. Let λ be a fixed γ-shape with s ≥ 1-arcs and m ≥ 0 1-arcs. Then the generating function of τ-canonical γ-diagrams containing 1-arcs that have shape λ containing 1-arcs 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}\widetilde {{\bf G}} _ {\tau , \gamma} (z) = (1 - z) ^ {- 1} \left(\frac {z^ {2 \tau}} {(1 - z^2) (1 - z) ^2 - (2z - z^2) z^ {2 \tau}} \right)^s.\end{align} \end{document} ■

7. Discussion

The symbolic approach based on γ-matchings allows not only for computing the generating function of canonical γ-structures. On the basis of Theorem 6, it is possible to obtain a plethora of statistics of γ-structures by means of combinatorial markers.

For instance, we can analogously compute the bivariate generating function of τ canonical γ-structures over n vertices, containing exactly m arcs, A_τ_,γ(z, t) 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 A} _ {\tau , \gamma} (z , t) = \frac {1} {u_ \tau (z , t) z^2 - z + 1} {\bf H} _ \gamma \left(\frac {u_ \tau (z , t) \ z^2} {(u_ \tau (z , t) z^2 - z + 1) ^2} \right) \tag {24} \end{align} \end{document}

where u_τ(z, t) 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}u_ \tau (z , t) = \frac {t \ (tz^2) ^ {\tau - 1}} {(tz^2) ^ {\tau} - tz^2 + 1} .\end{align} \end{document}

This bivariate generating function is the key to obtain a central limit theorem for the distribution of arc-numbers in γ-structures (Bender, 1973) on the basis of the Lévy-Cramér theorem on limit distributions (Feller, 1991).

Statistical properties of γ-structures play a key role for quantifying algorithmic improvements via sparsifications (Busch et al., 2008; Möhl et al., 2010; Wexler, 2007). The key property here is the polymer-zeta property (Kabakcioglu and Stella, 2008; Kafri et al., 2000), which states that the probability of an arc of length ℓ is bounded by k ℓ^c, where k is some positive constant and c > 1. Polymer-zeta stems from the theory of self-avoiding walks (Vanderzande, 1998) and has only been empirically established for the simplest class of RNA structures, namely those of genus zero. It turns out, however, that the polymer-zeta property is genuinely a combinatorial property of a structure class. Moreover, our results allow for quantifying the effect of sparsifications of folding algorithms into γ-structures (Andersen et al., 2012; Huang and Reidys, 2012).

We finally remark that around 98% of RNA pseudoknot structures catalogued in databases are, in fact, canonical 1-structures. RNA pseudoknot structures like the HDV virus exhibiting irreducible shadows of genus two are relatively rare.

(s, i)	(1, 1)	(2, 1)	(1, 2)	(2, 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} $$\rho^{- 1}_{s , i}$$ \end{document}	3.6005	2.2759	3.8846	2.3553

Footnotes

Acknowledgments

We thank Fenix W.D. Huang for discussions and comments. We furthermore acknowledge the financial support of the Future and Emerging Technologies (FET) program within the Seventh Framework Programme (FP7) for Research of the European Commission, under the FET-Proactive grant agreement TOPDRIM, number FP7-ICT-318121.

Author Disclosure Statement

The authors declare that no competing financial interests exist.

References

Andersen

J.E.

, Huang

F.W.D.

, Penner

R.C.

, et al. 2012. Topology of RNA-interaction structures. J. Comput. Biol., 19, 928–943.

Andersen

J.E.

, Penner

R.C.

, Reidys

C.M.

, et al. 2013. Topological classification and enumeration of rna structures by genus. J. Math. Biol., 67, 1261–1278.

Bailor

M.H.

, Sun

, and Al-Hashimi

H.M.

2010. Topology links RNA secondary structure with global conformation, dynamics, and adaptation. Science, 327, 202–206.

Bender

E.A.

1973. Central and local limit theorems applied to asymptotic enumeration. J. Combin. Theory A, 15, 91–111.

Bon

, Vernizzi

, Orland

, et al. 2008. Topological classification of RNA structures. J. Mol. Biol., 379, 900–911.

Busch

, Richter

A.S.

, and Backofen

2008. IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions. Bioinformatics, 24, 2849–2856.

Dyson

F.J.

1949. The S matrix in quantum electrodynamics. Phys. Rev., 75, 1736–1755.

Feller

1991. An Introduction to Probability Theory and Its Application. Addison-Wesley Publishing Company Inc., New York.

Flajolet

, and Sedgewick

2009. Analytic Combinatorics. Cambridge University Press, New York.

10.

Harer

, and Zagier

1986. The euler characteristic of the moduli space of curves. Invent. Math., 85, 457–486.

11.

Hille

1962. Analytic Function Theory, Volume II. Chelsea Publishing Company.

12.

Huang

F.W.D.

, and Reidys

C.M.

2012. On the combinatorics of sparsification. Algorithm. Mol. Biol., 7, 28.

13.

Kabakcioglu

, and Stella

A.L.

2008. A scale-free network hidden in the collapsing polymer. Bioinformatics.

14.

Kafri

, Mukamel

, and Peliti

2000. Why is the DNA denaturation transition first order?. Phys. Rev. Lett., 85, 4988–4991.

15.

Loebl

, and Moffatt

2008. The chromatic polynomial of fatgraphs and its categorification. Adv. Math., 217, 1558–1587.

16.

Massey

W.S.

1967. Algebraic Topology: An Introduction. Springer-Verlag, New York.

17.

Möhl

, Salari

, Will

, et al. 2010. Sparsification of RNA structure prediction including pseudoknots. Algorithms for Molecular Biology, 5, 39.

18.

Nebel

M.E.

, and Weinberg

2011. Algebraic and combinatorial properties of common RNA pseudoknot classes with applications. J. Comput. Biol., 19, 1134–1150.

19.

Orland

, and Zee

2002. RNA folding and large n matrix theory. Nuclear Physics B, 620, 456–476.

20.

Penner

R.C.

2004. Cell decomposition and compactification of Riemann's moduli space in decorated Teichmüller theory, 263–301. In Tongring

, and Penner

R.C.

, eds. Woods Hole Mathematics-Perspectives in Math and Physics, pages 263–301. World Scientific, Singapore.

21.

Penner

R.C.

, Knudsen

, Wiuf

, et al. 2010. Fatgraph models of proteins. Comm. Pure Appl. Math., 63, 1249–1297.

22.

Penner

R.C.

, and Waterman

M.S.

1993. Spaces of RNA secondary structures. Adv. Math., 101, 31–49.

23.

Reidys

C.M.

, Huang

F.W.D.

, Andersen

J.E.

, et al. 2011. Topology and prediction of RNA pseudoknots. Bioinformatics, 27, 1076–1085.

24.

Smith

T.F.

, and Waterman

M.S.

1978. RNA secondary structure. Math. Biol., 42, 31–49.

25.

Tabaska

J.E.

, Cary

R.B.

, Gabow

H.N.

, et al. 1998. An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics, 14, 691–699.

26.

Vanderzande

1998. Lattice Models of Polymers. Cambridge University Press, New York.

27.

Wall

C.T.C.

2004. Singular Points of Plane Curves. Cambridge University Press, New York.

28.

Wexler

, Zilberstein

, Ziv-ukelson

2007. A study of accessible motifs and RNA folding complexity. J. Comput. Biol., 14, 6.