Drube, Paul; Pongtanapaisan, Puttipong

Annular non-crossing matchings

J. Integer Seq. 19(2), Article 16.2.4, 17 p., electronic only (2016)

Summary

Summary: It is well known that the number of distinct non-crossing matchings of $n$ half-circles in the half-plane with endpoints on the $x$-axis equals the $n^{th}$ Catalan number $C_{n}$. This paper generalizes that notion of linear non-crossing matchings, as well as the circular non-crossing matchings of Goldbach and Tijdeman, to non-crossings matchings of curves embedded within an annulus. We prove that the number of such matchings | $Ann(n, m)$ | with $n$ exterior endpoints and $m$ interior endpoints correspond to an entirely new, one-parameter generalization of the Catalan numbers with $C_{n} = | Ann(2n + 1, 1)$ |. We also develop bijections between specific classes of annular non-crossing matchings and other combinatorial objects such as binary combinatorial necklaces and planar graphs. Finally, we use Burnside's lemma to obtain an explicit formula for | $Ann(n, m)$ | for all integers $n, m \ge 0$.

Keywords/Phrases

non-crossing matching, combinatorial necklace, Catalan number

Downloads