Asymptotic analysis of $k$-noncrossing matchings

Abstract

In this paper we study $k$-noncrossing matchings. A $k$-noncrossing matching is a labeled graph with vertex set $\{1,...,2n\}$ arranged in increasing order in a horizontal line and vertex-degree 1. The $n$ arcs are drawn in the upper halfplane subject to the condition that there exist no $k$ arcs that mutually intersect. We derive: (a) for arbitrary $k$, an asymptotic approximation of the exponential generating function of $k$-noncrossing matchings $F_k(z)$. (b) the asymptotic formula for the number of $k$-noncrossing matchings $f_k(n)\sim c_k{n}^{-((k-1{)}^2+(k-1)/2)}(2(k-1){)}^{2n}$ for some $c_k>0$.

19 pages and 1 figure

Cited by in corpus (2)

• Canonical RNA pseudoknot structures
• Stacks in canonical RNA pseudoknot structures