##
**
Annular Non-Crossing Matchings
**

###
Paul Drube and Puttipong Pongtanapaisan

Department of Mathematics and Statistics

Valparaiso University

Valparaiso, IN 46383

USA

**Abstract:**

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(2*n* + 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**