Journal of Integer Sequences, Vol. 19 (2016), Article 16.2.4

Annular Non-Crossing Matchings

Paul Drube and Puttipong Pongtanapaisan
Department of Mathematics and Statistics
Valparaiso University
Valparaiso, IN 46383


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 nth Catalan number Cn. 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 Cn = | 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 ≥ 0.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A002995 A003239 A003441 A007595 A047996 A241926.)

Received August 7 2015; revised versions received December 15 2015; December 18 2015. Published in Journal of Integer Sequences, January 10 2016.

Return to Journal of Integer Sequences home page