Annular non-crossing matchings

Drube, Paul ; Pongtanapaisan, Puttipong

Journal of integer sequences, Tome 19 (2016) no. 2

Résumé

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$.

Détail

Keywords: non-crossing matching, combinatorial necklace, Catalan number