Annular Non-Crossing Matchings
Paul Drube and Puttipong Pongtanapaisan
Department of Mathematics and Statistics
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
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,
(Concerned with sequences
Received August 7 2015; revised versions received December 15 2015; December 18 2015.
Published in Journal of Integer Sequences, January 10 2016.
Journal of Integer Sequences home page