\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage[margin=2cm]{geometry}
\usepackage{array}
\usepackage{tikz}
\usetikzlibrary{arrows,shapes,positioning,decorations.markings}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\Ann}{Ann}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Annular Non-Crossing Matchings
}
\vskip 1cm
\large
Paul Drube and Puttipong Pongtanapaisan\\
Department of Mathematics and Statistics\\
Valparaiso University\\
Valparaiso, IN 46383\\
USA\\
\href{mailto:Paul.Drube@valpo.edu}{\tt Paul.Drube@valpo.edu} \\
\href{mailto:Puttipong.Pongtanapaisan@valpo.edu}{\tt Puttipong.Pongtanapaisan@valpo.edu}\\
\end{center}
\vskip .2 in
\def\N{\mathbb{N}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\begin{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^{\rm 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 \geq 0$.
\end{abstract}
\section{Introduction}
\label{sec:background}
The Catalan numbers are arguably the most studied sequence of positive integers in mathematics. Among their seemingly countless combinatorial interpretations is an identification of the $n^{th}$ Catalan number $C_n = \frac{1}{n+1} \binom{2n}{n}$ with non-crossing matchings of $2n$ points along the $x$-axis via $n$ half-circles in the upper half-plane. In an effort to avoid confusion, we will sometimes refer to such arrangements as linear non-crossing matchings of order $n$. The $n^{th}$ Catalan number is also known to equal the number of ordered rooted trees with $n$ non-root vertices. One bijection between these two interpretations is shown in Figure \ref{fig:matchings_to_trees,_half-plane}. That map involves placing a vertex in each region of the complement of a matching, with the ``external" region receiving the root vertex, and then adding an edge if two regions are separated by a half-circle. For an extended treatment of the many different interpretations of Catalan numbers and the bijections between them, see Stanley \cite{Stanley}.
\begin{figure}[ht!]
\centering
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,fill=black,inner sep=0pt}]
\node[inner sep=0pt] (left) at (0,0) {};
\node (1) at (1,0) {};
\node (2) at (1.8,0) {};
\node (3) at (3.2,0) {};
\node (4) at (3.8,0) {};
\node (5) at (5.2,0) {};
\node (6) at (6,0) {};
\node (7) at (6.9,0) {};
\node (8) at (7.8,0) {};
\node (9) at (9.2,0) {};
\node (10) at (10.1,0) {};
\node[inner sep=0pt] (right) at (11,0) {};
\draw[thick] (left) to (right);
\draw[thick] (3.2,0) arc (0:180:.7);
\draw[thick] (5.2,0) arc (0:180:.7);
\draw[thick] (6,0) arc (0:180:2.5);
\draw[thick] (10.1,0) arc (0:180:1.6);
\draw[thick] (9.2,0) arc (0:180:.7);
\node[fill=white,draw,inner sep=1.5pt,thick] (n1) at (6.4,3) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (3.5,1.5) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (8.5,1.1) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (2.5,0.25) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (4.5,0.25) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n6) at (8.5,0.25) {};
\end{tikzpicture}
\hspace{0.05in}
\scalebox{2.5}{\raisebox{5pt}{$\Leftrightarrow$}}
\hspace{0.05in}
\begin{tikzpicture}
[scale=0.4,auto=left,every node/.style={circle,fill=black,inner sep=2.5pt}]
\node[fill=white,draw,inner sep=1.5pt,thick] (n1) at (6,3) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (3.5,1.5) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (8.5,1.5) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (2.5,0.25) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (4.5,0.25) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n6) at (8.5,0.25) {};
\draw[thick] (n1) to (n2);
\draw[thick] (n1) to (n3);
\draw[thick] (n2) to (n4);
\draw[thick] (n2) to (n5);
\draw[thick] (n3) to (n6);
\end{tikzpicture}
\caption{The bijection between linear non-crossing matchings and ordered rooted trees.}
\label{fig:matchings_to_trees,_half-plane}
\end{figure}
Non-crossing matchings admit many interesting generalizations if one restricts curves to a subset of $\R^2$ that is not the upper half-plane. One such modification is what we refer to as circular non-crossing matchings. In a circular non-crossing matching of order $n$, $2n$ distinct points on the unit circle are connected by a set of $n$ non-intersecting smooth curves within the unit circle. Circular non-crossing matchings are considered equivalent if they differ by isotopies within the unit circle (including isotopies that ``slide" endpoints), as long as those isotopies do not result in curves or endpoints intersecting. In particular, circular matchings related by rotation about the center of the unit circle are equivalent. However, matchings that can only be related via reflections are considered distinct. We henceforth refer to the number of circular non-crossing matchings of order $n$, modulo these relations, by $\widetilde{C}_n$.
One in-depth study of circular non-crossing matchings was undertaken by Goldbach and Tijdeman \cite{GT}. In that work, an involved application of Burnside's lemma showed that:
\begin{equation}
\label{eq:Goldbach-Tijdeman_enumeration}
\widetilde{C}_n \ = \ \frac{1}{2n} \left( \sum_{d | n} \varphi(n/d) \binom{2d}{d} \right) - \frac{1}{2} C_n + \frac{1}{2} C_{(n-1)/2},
\end{equation}
where $\varphi(k)$ is Euler's totient function and $C_k$ is taken to be zero when $k$ is not an integer, so that the final term only appears when $n$ is odd.
Although not obvious from \eqref{eq:Goldbach-Tijdeman_enumeration}, there is also a bijection between circular non-crossing matchings of order $n$ and unrooted planar trees with $n+1$ nodes ($n$ edges). For an illustration of this bijection, see Figure \ref{fig:matchings_to_trees,_circular}. Notice that this correspondence identifies $\widetilde{C}_n$ with the $(n-1)^{st}$ entry of OEIS \seqnum{A002995}. See Harary and Palmer \cite{Harary} for further discussion of the graph-theoretic interpretations of $\widetilde{C}_n$.
\begin{figure}[ht!]
\centering
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\node[fill=black,draw,inner sep=1.5pt,thick] (n1) at (90:0.7) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (90:0.15) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (270:0.4) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (225:0.85) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (315:0.85) {};
\draw[thick, bend right=40] (140:1) to (40:1);
\draw[thick, bend right=40] (165:1) to (15:1);
\draw[thick, bend right=60] (340:1) to (280:1);
\draw[thick, bend right=60] (260:1) to (200:1);
\end{tikzpicture}
\hspace{0.3in}
\scalebox{2.5}{\raisebox{10pt}{$\Leftrightarrow$}}
\hspace{0.3in}
\begin{tikzpicture}
[scale=0.4,auto=left,every node/.style={circle,fill=black,inner sep=2.5pt,thick}]
\node(n1)[fill=black,draw,inner sep=1.5pt,thick] at (0,-2) {};
\node(n2)[fill=black,draw,inner sep=1.5pt,thick] at (0,-0.2) {};
\node(n3)[fill=black,draw,inner sep=1.5pt,thick] at (0,1.6) {};
\node(n4)[fill=black,draw,inner sep=1.5pt,thick] at (2,-2.8) {};
\node(n5)[fill=black,draw,inner sep=1.5pt,thick] at (-2,-2.8) {};
\draw[thick] (n1) to (n2);
\draw[thick] (n2) to (n3);
\draw[thick] (n4) to (n1);
\draw[thick] (n5) to (n1);
\end{tikzpicture}
\caption{The bijection between circular non-crossing matchings and unrooted planar trees.}
\label{fig:matchings_to_trees,_circular}
\end{figure}
In this paper we introduce a new, two-parameter generalization of linear non-crossing matchings in which our smooth curves are embedded within an annulus. So let $n,m$ be non-negative integers such that $n+m$ is even. We define an \textit{annular non-crossing matching of type $(n,m)$} to be a collection of $\frac{n+m}{2}$ non-intersecting smooth curves within the annulus whose endpoints lie at $n+m$ distinct points along the annulus, with $n$ of those endpoints on the exterior boundary of the annulus and $m$ of those endpoints on the interior boundary of the annulus. Two annular matchings are considered equivalent if they differ by isotopies within the annulus (including isotopies that ``slide" endpoints), as long as those isotopies don't result in curves or endpoints intersecting. Annular matchings that can only be related by reflections are considered distinct; also disallowed are isotopies where an edge must pass through the hole in the middle of the annulus. We denote the set of annular non-crossing matchings of type $(n,m)$, modulo these relations, by $\Ann(n,m)$. If we wish to reference the larger collection of all annular non-crossing matchings with $N$ total endpoints, no matter how those endpoints are partitioned between inner and outer boundary components, we write $\Ann(N)$. Thus $\Ann(N) = \lbrace M \in \Ann(n,m) \ \vert \ n+m = N \rbrace$ and $\Ann(N) \neq 0$ if and only if $N$ is even.
In many settings, it will be advantageous to sub-divide annular matchings according to the the number of curves that do not isotope to half-circles on one boundary component. We define a \textit{cross-cut} to be a curve in an annular non-crossing matching with one endpoint on the inside of the annulus and one endpoint on the outside of the annulus. We denote the set of annular non-crossing matchings of type $(n,m)$ with precisely $k$ cross-cuts by $\Ann_k(n,m)$, so that $\Ann(n,m) = \bigcup_k \Ann_k(n,m)$. See Figure \ref{fig:annular_matchings_examples} for several quick examples.
\begin{figure}[ht!]
\centering
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (165:1) to (165:0.35);
\draw[thick] (15:1) to (15:0.35);
\draw[thick] (50:0.35) arc (-13:198:0.25) ;
\draw[thick, bend right=45] (313:1) to (228:1);
\draw[thick, bend right=60] (290:1) to (250:1);
\end{tikzpicture}
\hspace{.7in}
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick, bend left=45] (0:1) to (60:1);
\draw[thick, bend left=45] (120:1) to (180:1);
\draw[thick, bend left=45] (240:1) to (300:1);
\end{tikzpicture}
\caption{An element of $\Ann_2(6,4)$, and an element of $\Ann_0(6,0)$.}
\label{fig:annular_matchings_examples}
\end{figure}
Observe that every annular matching may be isotoped so that all of its cross-cuts appear as straight chords that meet both boundary circles at a right angle. Also notice that $| \Ann_k(n,m)\, | = 0$ unless $n-k$ and $m-k$ are both even. When working with an element of $\Ann_k(n,m)$, we will sometimes refer to the $(n-k)/2$ curves with both endpoints on the outside of the annulus as ``external half-circles", and to the $(m-k)/2$ curves with both endpoints on the inside of the annulus as ``internal half-circles".
\subsection{Outline of results}
\label{subsec:outline_of_results}
The primary goal of this paper is to enumerate $| \Ann(n,m)\, |$ for arbitrary non-negative integers $n$ and $m$. This will be accomplished by enumerating $| \Ann_k(n,m) |$ for arbitrary integers $n,m,k$ and then summing over $k$. Section \ref{sec:basic_annular_results} will begin the process with a series of basic results about annular non-crossing matchings, laying the theoretical framework for our subsequent enumerations. Along the way we will demonstrate a bijection between elements of $\Ann_k(n,m)$ and sets of planar graphs that possess a single $k$-cycle and no cycles of any other size (Proposition \ref{thm:graph_interpretation,_no_crosscuts}, Theorem \ref{thm:graph_interpretation,_general}).
Section \ref{sec:enumeration} presents our enumerative results. Subsection \ref{subsec:m=0_enumeration_and_necklaces} begins with a consideration of the sets $\Ann_k(2n+k,k)$, a sub-case that we refer to as ``maximal cross-cut annular matchings". Burnside's lemma will be used to prove the following, which later appears as Theorem \ref{thm:maximal_cross-cut_direct_enumeration}.
\begin{theorem}
\label{thm:intro_theorem_1}
Let $n$ and $k$ be non-negative integers. Then
$$
| \Ann_k(2n+k,k)\, | =
\begin{cases}
1, & \text{\ if \ } n=k=0;\\[1em]
\displaystyle{\frac{1}{2n+k} \sum_{d | \gcd(k,n)} \kern-4pt \varphi(d) \binom{(2n+k)/d}{n/d}}, & \text{\ otherwise};
\end{cases}
$$
where $\varphi(d)$ is Euler's totient function.
\end{theorem}
Subsection \ref{thm:maximal_cross-cut_direct_enumeration} will also exhibit a direct bijection between these maximal cross-cut annular matchings and binary combinatorial necklaces. If $N_2(n_1,n_2)$ denotes the number of binary combinatorial necklaces with $n_1$ black beads and $n_2$ white beads, then Theorem \ref{thm:annular_matchings_=_necklaces} will prove the following statement.
\begin{theorem}
\label{thm:_intro_theorem_2}
Let $n$ and $k$ be non-negative integers. Then $| \Ann_k(2n+k,k)\, | = N_2(n+k,n)$.
\end{theorem}
Our results for $| \Ann_k(2n+k,k)\, |$ are then used in Subsection \ref{subsec:enumeration_general} to enumerate $| \Ann_k(2n+k,2m+k) |$ for the remaining choices of $n$, $m$, and $k$. In particular, Theorem \ref{thm:general_enumeration} will prove the result below.
\begin{theorem}
\label{thm:_intro_theorem_3}
Let $n,m,k$ be non-negative integers. Then
$$
| \Ann_k(2n+k,2m+k)\, | =
\begin{cases}
| \Ann_0(2n,0) | \cdot | \Ann_0(2m,0) |, & \text{if \ }k = 0;\\[1em]
\displaystyle{\frac{k}{(2n+k)(2m+k)} \sum_{d | \gcd(k,n,m)} \kern-16pt \varphi(d) \binom{(2n+k)/d}{n/d} \binom{(2m+k)/d}{m/d}}, & \text{if \ } k > 0;
\end{cases}
$$
where $\varphi(d)$ is Euler's totient function.
\end{theorem}
We close the paper with an appendix of tables giving outputs for $| \Ann(n,m)\, |$, $| \Ann_k(n,m)\, |$, and $| \Ann(N)\, |$, all calculated in Maple using Theorems \ref{thm:maximal_cross-cut_direct_enumeration} and \ref{thm:general_enumeration}.
\section{Basic results about annular non-crossing matchings}
\label{sec:basic_annular_results}
In this section we present a series of fundamental results about annular non-crossing matchings, some of which will be utilized to prove the more general enumerative results of Section \ref{sec:enumeration}. We also take the opportunity to draw bijections between annular matchings and various classes of planar graphs, and relate the number of ``zero cross-cut" matchings in $\Ann(2n,0)$ to $C_n$ and $\widetilde{C}_n$.
\begin{proposition}
\label{thm:reflection_equivalence}
Let $n,m$ be non-negative integers. Then $| \Ann_k(n,m)\, | = | \Ann_k(m,n)\, |$ for all $k \geq 0$. In particular, $| \Ann(n,m)\, | = | \Ann(m,n)\, |$ for all $n,m \geq 0$.
\end{proposition}
\begin{proof}
Begin by isotoping elements of $\Ann_k(n,m)$ and $\Ann_k(m,n)$ so that all cross-cuts appear as straight chords orthogonal to the boundary circles. Reflection across the ``core" of the annulus then maps every cross-cut to itself, and defines a bijection between $\Ann_k(n,m)$ and $\Ann_k(m,n)$ for any $k \geq 0$.
\end{proof}
The primary use of Proposition \ref{thm:reflection_equivalence} is that it will allow us to restrict our attention to $\Ann(n,m)$ and $\Ann_k(n,m)$ such that $n \geq m$. Yet even within the realm where $n \geq m$, there will be specific ``easy" choices for $n$ and $m$ that will prove to have the most useful combinatorial interpretations. The first of these special cases is $\Ann(2n,0) = \Ann_0(2n,0)$, corresponding to the situation where all curves in the matchings are external half-circles.
\begin{proposition}
\label{thm:graph_interpretation,_no_crosscuts}
Let $n$ be any non-negative integer. Then $| \Ann(2n,0)\, |$ equals the number of unrooted trees with a distinguished vertex and $n$ additional vertices.
\end{proposition}
\begin{proof}
The required bijection is analogous to the constructions of Figures \ref{fig:matchings_to_trees,_half-plane} and \ref{fig:matchings_to_trees,_circular} for linear and circular matchings. We add one vertex for each region in the matching and connect two vertices with an edge if they are separated by a half-circle:
\begin{center}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick, bend left=40] (87:1) to (143:1);
\draw[thick, bend left=30] (65:1) to (165:1);
\draw[thick, bend left=45] (210:1) to (270:1);
\draw[thick, bend left=45] (300:1) to (0:1);
\node[fill=white,draw,inner sep=2.2pt,thick] (n1) at (30:.7) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (115:.85) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (90:.7) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (240:.85) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (330:.85) {};
\end{tikzpicture}
\hspace{0.3in}
\scalebox{2.5}{\raisebox{10pt}{$\Leftrightarrow$}}
\hspace{0.3in}
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\node[fill=white,draw,inner sep=2.2pt,thick] (n1) at (30:.7) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (115:.85) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (90:.7) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (240:.85) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (330:.85) {};
\draw[thick] (n1) to (n3);
\draw[thick] (n3) to (n2);
\draw[thick] (n1) to (n4);
\draw[thick] (n1) to (n5);
\end{tikzpicture}
\end{center}
Here the distinguished vertex is placed in the sole region that borders the interior boundary of the annulus. In placing the edges for our graph, we disregard whether that edge would have passed through the hole in the center of the annulus (we treat the hole as part of the internal region). As the half-circles in our matchings may be cyclically rotated around the center of the annulus in ``blocks", this gives us the desired notion of equivalence for our trees.
\end{proof}
Notice that the class of planar graphs from Proposition \ref{thm:graph_interpretation,_no_crosscuts} is not equivalent to rooted trees with $n+1$ vertices, as we allow for cyclic reordering of subtrees around the distinguished vertex. The construction of Proposition \ref{thm:graph_interpretation,_no_crosscuts} does identify $| \Ann(2n,0)\, |$ with the $n^{th}$ entry of OEIS \seqnum{A003239}. See Harary and Palmer \cite{Harary} or Stanley \cite{Stanley2} for further bijections involving $| \Ann(2n,0)\, |$.
Via the planar graph bijections of Section \ref{sec:background} and Proposition \ref{thm:graph_interpretation,_no_crosscuts}, it is immediate that $\widetilde{C}_n \leq | \Ann(2n,0)\, | \leq C_n$ for all $n \geq 0$. One can easily verify that $\widetilde{C}_n = | \Ann(2n,0)\, | = C_n$ for both $n=0$ and $n=1$. For $n=2$ we have $| \Ann(4,0)\, | = C_2 =2$ yet $\widetilde{C}_2 = 1$. As shown in the following proposition, $n=2$ is the largest value of $n$ for which any of the three quantities are equal.
\begin{proposition}
\label{thm:zero_crosscuts_inequalities}
For all $n \geq 3$ we have $\widetilde{C}_n < | \Ann(2n,0)\, | < C_n$.
\end{proposition}
\begin{proof}
We define a map $\phi$ from the set of all linear non-crossings of order $n$ to $\Ann(2n,0)$ by identifying the endpoints of the $x$-axis and placing the resulting circle as the outer boundary of the annulus. We then define a map $\psi$ from $\Ann(2n,0)$ to the set of all circular non-crossing matchings of order $n$ by ``deleting" the hole in the middle of the annulus.
\begin{center}
\raisebox{24pt}{$\phi ($
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,fill=black}]
\node[inner sep=0pt] (left) at (0,0) {};
\node[inner sep=0pt] (right) at (1.5,0) {};
\draw[thick] (left) to (right);
\put(15,1){$A$}
\end{tikzpicture}
$) \ = \ $}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw (0,0) circle (.35cm);
\node (A) at (270:.8) {A};
\end{tikzpicture}
\hspace{.5in}
\raisebox{24pt}{$\psi ($}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw (0,0) circle (.35cm);
\node (A) at (270:.8) {A};
\end{tikzpicture}
\raisebox{24pt}{$) \ = \ $}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\node (A) at (270:.8) {A};
\end{tikzpicture}
\end{center}
Both $\phi$ and $\psi$ are clearly well-defined and surjective for all $n \geq 0$. To see that neither map is injective, we construct a counterexample to injectivity that simultaneously holds for all $n \geq 3$. If $A$ is any non-empty block of half-circles, then the (distinct) linear non-crossing matchings on the left of the subsequent image map to the same annular non-crossing matching via $\phi$, while the (distinct) annular non-crossing matchings on the right of the subsequent image map to the same circular non-crossing matching via $\psi$.
\begin{center}
\raisebox{18pt}{
\raisebox{4pt}{$\phi ($}
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,fill=black,inner sep=0pt}]
\node[inner sep=0pt] (left) at (1,0) {};
\node[inner sep=0pt] (right) at (6,0) {};
\draw[thick] (left) to (right);
\draw[thick] (4.5,0) arc (0:180:.5);
\draw[thick] (5.5,0) arc (0:180:1.5);
\put(20,1){$A$}
\end{tikzpicture}
\raisebox{4pt}{$) \ = \ \phi ($}
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,fill=black,inner sep=0pt}]
\node[inner sep=0pt] (left) at (1,0) {};
\node[inner sep=0pt] (right) at (6,0) {};
\draw[thick] (left) to (right);
\draw[thick] (4.5,0) arc (0:180:1.5);
\draw[thick] (3.5,0) arc (0:180:.5);
\put(70,1){$A$}
\end{tikzpicture}
\raisebox{4pt}{$)$}}
\hspace{.5in}
\raisebox{24pt}{$\psi ($}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt,fill=none}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick,bend left=60] (270:1) to (340:1);
\node (A) at (235:.8) {A};
\end{tikzpicture}
\raisebox{24pt}{$) \ = \ \psi ($}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt,fill=none}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick,bend left=60] (200:1) to (270:1);
\node (A) at (235:.8) {A};
\end{tikzpicture}
\raisebox{24pt}{$)$}
\end{center}
\end{proof}
With the zero cross-cuts case well-understood, we expand our attention to $\Ann_k(n,m)$ with $k \geq 1$. In what follows we re-index variables to consider $\Ann_k(2n+k,2m+k)$, as this alternative notation explicitly references the presence of $n$ external half-circles and $m$ internal half-circles. The cases that will prove most useful are what we refer to as \textit{maximal cross-cut annular matchings}. In maximal cross-cut annular matchings, the only endpoints on the interior boundary belong to cross-cuts. In our new notation this implies that $m=0$, so that we are dealing with sets of the form $\Ann_k(2n+k,k)$. Notice that the previously considered sets $\Ann(2n,0) = \Ann_0(2n+0,0)$ qualify as maximal cross-cut annular matchings.
When $k=1$, maximal cross-cut annular matchings are counted by the Catalan numbers, namely $\Ann_1(2n+1,1) = C_n$. As shown in Figure \ref{fig:1_crosscut_equals_Catalan_numbers}, a bijection of such annular matchings with linear non-crossing matchings is realized by identifying the outer boundary of the annulus with the real line, in such a way that the outer endpoint of the sole cross-cut corresponds to $\pm \infty$.
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt,fill=none}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (90:1) to (90:0.35);
\node (A) at (270:.8) {A};
\end{tikzpicture}
\hspace{0.3in}
\scalebox{2.5}{\raisebox{10pt}{$\Leftrightarrow$}}
\hspace{0.3in}
\raisebox{18pt}{
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,fill=black}]
\node[inner sep=0pt] (left) at (0,0) {};
\node[inner sep=0pt] (right) at (2.5,0) {};
\draw[thick] (left) to (right);
\node[fill=none] (A) at (1.25,.2) {A};
\end{tikzpicture}}
\end{center}
\caption{The bijection between $\Ann_1(2n+1,1)$ and linear non-crossing matchings of order $n$.}
\label{fig:1_crosscut_equals_Catalan_numbers}
\end{figure}
Maximal cross-cut annular matchings will be directly enumerated in Subsection \ref{subsec:m=0_enumeration_and_necklaces} for all $k \geq 0$, and those enumerations will be necessary building blocks for the general enumerations of Subsection \ref{subsec:enumeration_general}. Although the full importance of the maximal cross-cut case will not become obvious until those subsections, we pause to prove one useful property shared by maximal cross-cut matchings and annular matchings with zero cross-cuts.
\begin{proposition}
\label{thm:splitting_into_one-sided_product}
Let $n,m,k$ be non-negative integers. If $m=0$ or $k=0$ then
$$
| \Ann_k (2n+k,2m+k)\, | = | \Ann_k(2n+k,k)\, | \cdot | \Ann_k(2m+k,k)\, |
$$
\end{proposition}
\begin{proof}
We define a general map $\phi: \Ann_k(2n+k,2m+k) \rightarrow \Ann_k(2n+k,k) \oplus \Ann_k(k,2m+k)$ that becomes a bijection when $m=0$ or $k=0$. This $\phi$ is defined by deleting internal half-circles in the first coordinate of the output and deleting external half-circles in the second coordinate, as in the example below.
\begin{center}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (180:1) to (180:0.35);
\draw[thick] (0:1) to (0:0.35);
\draw[thick] (50:0.35) arc (-13:198:0.25) ;
\draw[thick, bend right=45] (313:1) to (228:1);
\draw[thick, bend right=60] (290:1) to (250:1);
\draw[thick, bend left=60] (35:1) to (75:1);
\draw[thick, bend left=60] (105:1) to (145:1);
\end{tikzpicture}
\hspace{4pt}
\raisebox{22pt}{\scalebox{2.2}{$\mapsto$}}
\hspace{1pt}
\raisebox{17pt}{\scalebox{3.5}{$($}}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (180:1) to (180:0.35);
\draw[thick] (0:1) to (0:0.35);
\draw[thick, bend right=45] (313:1) to (228:1);
\draw[thick, bend right=60] (290:1) to (250:1);
\draw[thick, bend left=60] (35:1) to (75:1);
\draw[thick, bend left=60] (105:1) to (145:1);
\end{tikzpicture}
\hspace{-10pt}
\raisebox{5pt}{\scalebox{2.0}{$\ , \ $}}
\hspace{-10pt}
\begin{tikzpicture}
[scale=1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (180:1) to (180:0.35);
\draw[thick] (0:1) to (0:0.35);
\draw[thick] (50:0.35) arc (-13:198:0.25) ;
\end{tikzpicture}
\raisebox{17pt}{\scalebox{3.5}{$)$}}
\end{center}
This map $\phi$ is clearly a bijection whenever $m=0$. To see that $\phi$ is a bijection when $k=0$, notice that the lack of cross-cuts in the $k=0$ case means that the internal half-circles and external half-circles may be isotoped independently around their respective boundary components and hence ``do not interact".
\end{proof}
It can be shown that the equality of Proposition \ref{thm:splitting_into_one-sided_product} holds precisely when $n=0$ or $m=0$ or $k<2$. If $k \geq 2$, $n \geq 1$, and $m \geq 1$ all hold, the left side of the expression always proves to be strictly larger than the right side. However, only the $m = 0$ and $k = 0$ cases are needed in Section \ref{sec:enumeration}, motivating our omission of the more general result.
For our final result of this section, we adapt the planar graph bijection of Proposition \ref{thm:graph_interpretation,_no_crosscuts} to the general case of $\Ann_k(2n+k,2m+k)$. Although the resulting language of Theorem \ref{thm:graph_interpretation,_general} is arguably rather contrived, it combines with Proposition \ref{thm:graph_interpretation,_no_crosscuts} to give a succinct geometric characterization of any class of annular matchings with at least one cross-cut.
\begin{theorem}
\label{thm:graph_interpretation,_general}
Let $n,m,k$ be non-negative integers and let $k \geq 1$. Then $| \Ann_k(2n+k,2m+k)\, |$ equals the number of connected planar graphs such that:
\begin{enumerate}
\item The only cycle in the graph is a single $k$-cycle.
\item There are $n$ edges within the area bounded by the cycle.
\item There are $m$ edges outside the area bounded by the cycle.
\end{enumerate}
\end{theorem}
\begin{proof}
The methodology used is extremely similar to what has already been presented in Proposition \ref{thm:graph_interpretation,_no_crosscuts}. Notice that a collection of $k$ cross-cuts produces a single $k$-cycle, as shown below.
\begin{center}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick] (0:1) to (0:.35);
\draw[thick] (72:1) to (72:.35);
\draw[thick] (144:1) to (144:.35);
\draw[thick] (216:1) to (216:.35);
\draw[thick] (288:1) to (288:.35);
\node[fill=black,draw,inner sep=1.5pt,thick] (n1) at (36:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (108:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (180:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (252:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (324:.725) {};
\end{tikzpicture}
\hspace{0.3in}
\scalebox{2.5}{\raisebox{10pt}{$\Leftrightarrow$}}
\hspace{0.3in}
\raisebox{6pt}{
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\node[fill=black,draw,inner sep=1.5pt,thick] (n1) at (36:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n2) at (108:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n3) at (180:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n4) at (252:.725) {};
\node[fill=black,draw,inner sep=1.5pt,thick] (n5) at (324:.725) {};
\draw[thick] (n1) to (n2);
\draw[thick] (n2) to (n3);
\draw[thick] (n3) to (n4);
\draw[thick] (n4) to (n5);
\draw[thick] (n5) to (n1);
\end{tikzpicture}}
\end{center}
Any internal half-circles are then counted by edges inside the $k$-cycle, while external half-circles are counted by edges outside the $k$-cycle.
\end{proof}
\section{Enumeration of annular non-crossing matchings}
\label{sec:enumeration}
We are now ready for the general enumerative results that form the core of this paper. Subsection \ref{subsec:m=0_enumeration_and_necklaces} begins with an enumeration of maximal cross-cut annular matchings, and shows that those matchings are in bijection with certain types of binary combinatorial necklaces. Subsection \ref{subsec:enumeration_general} then collects all of our results to give an explicit formula for general $| \Ann_k(n,m)\, |$, thus allowing for the direct calculation of $| \Ann(n,m)\, |$ and $| \Ann(N)\, |$. As in Section \ref{sec:basic_annular_results}, when the number of cross-cuts is specified we will typically re-index variables and treat $| \Ann_k(2n+k,2m+k)\, |$ so that the number of internal and external half-circles are immediately discernible.
\subsection{Enumeration of maximal cross-cut annular matchings and combinatorial necklaces}
\label{subsec:m=0_enumeration_and_necklaces}
Burnside's lemma has already been mentioned as the method used in Goldbach and Tijdeman \cite{GT} to calculate the number of circular non-crossing matchings. Given that our annular non-crossing matchings possess a similar notion of rotational equivalence, it comes as little surprise that the lemma may also be applied to the enumeration of distinct matchings in the annulus. Recall that Burnside's lemma (also known as the Cauchy-Frobenius lemma) applies to any situation where a finite group $G$ acts upon a set $A$. It asserts that the number of orbits $| A/G |$ with respect to the action equals the average size of the sets $A^g = \lbrace a \in A \ \vert \ ga = a \rbrace$ when ranging over all $g \in G$, that is $| A/G | = \frac{1}{| G |} \sum_{g \in G} | A^g |$.
So fix $n,k \geq 0$, and let $A$ equal the set of all non-crossing matchings in the annulus (prior to any notion of equivalence) with $2n+k$ endpoints located at $\frac{2\pi}{2n+k}$ radian intervals about the exterior boundary and precisely $k$ straight cross-cuts that meet both boundary components orthogonally. We may define a (left) action of $G = \Z_{2n+k}$ on $A$ whereby $g \cdot a$ is counter-clockwise rotation of $a$ by $\frac{2\pi g}{2n+k}$ radians. Then $| A/G | = | \Ann_k(2n+k,k)\, |$, with distinct orbits in $A/G$ corresponding to matchings that are equivalent via rotation. This sets up the following application of Burnside's lemma:
\begin{theorem}
\label{thm:maximal_cross-cut_direct_enumeration}
Let $n$ and $k$ be non-negative integers. Then
$$
| \Ann_k(2n+k,k)\,| =
\begin{cases}
1, & \text{\ if \ } n=k=0;\\[1em]
\displaystyle{\frac{1}{2n+k} \sum_{d | \gcd(k,n)} \kern-4pt \varphi(d) \binom{(2n+k)/d}{n/d}}, & \text{\ otherwise};
\end{cases}
$$
where $\varphi(d)$ is Euler's totient function.
\end{theorem}
\begin{proof}
The first case follows immediately, as there is a single ``empty" annular non-crossing matching. For the second case, if we use the aforementioned group action and Burnside's lemma we merely need to show that $ \sum_{g \in \Z_{2n+k}} | A^g | = \sum_{d | (2n+k,n)} \varphi(d) \binom{(2n+k)/d}{n/d}$. So take $g \in \Z_{2n+k}$, and assume that $g$ has order $d$ in $\Z_{2n+k}$ Notice that Lagrange's theorem guarantees $d \mid (2n+k)$, although it may or may not be true that $d \mid n$.
The elements of $A^g$ are those matchings that can be radially divided into $d$ identical sub-matchings. Each of these sub-arrangements features $(2n+k)/d$ endpoints on the outer boundary of the annulus, $k/d$ of which are the outer endpoints of cross-cuts and $n/d$ of which are left-endpoints of exterior half-circles. Notice that, when dividing an element of $A^g$ into sub-matchings, it may be that the two endpoints of a specific half-circle lie in different sub-matchings, so long as each of the sub-matchings features an identical arrangements of such half-circles. Further notice that each sub-matching must contain just as many ``outgoing" half-circles whose left-endpoint is in that sub-matching as it contains ``incoming" half-circles whose right-endpoint is in that sub-matching.
Now if $d \nmid n$, the left-endpoints of the external half-circles cannot be evenly sub-divided into sub-matchings as described above and we may conclude that $| A^g | = 0$. However, $d \mid n$ and $d \mid k$ together guarantee that $d \mid (2n+k)$, making $| A^g | \neq 0$ a possibility in that case. If $d \mid n$, notice that every possible sub-arrangement may be uniquely identified by specifying which of the $(2n+k)/d$ endpoints correspond to left (clockwise) endpoints of exterior half-circles. To explicitly see that $| A^g | = \binom{(2n+k)/d}{n/d}$, we proceed as below.
\begin{enumerate}
\item Begin with any linear arrangement of $(2n+k)/d$ points of the $x$-axis, $n/d$ of which are white and $(n+k)/d$ of which are black. Although we do not close the $x$-axis off into a circle, we consider the cyclic ordering of these points (so that the rightmost point is considered to be directly left of the leftmost point).
\item Identify all white points that lie directly left of a black point (in the cyclic ordering) and make those points the left endpoints of external half-circles whose right-endpoints are the black points on their right. If the resulting half-circle ``wraps around" in the cyclic ordering, split it in two as an ``outgoing" strand and an ``incoming" strand. These will correspond to half-circles whose endpoints are split between sub-matchings in the resulting annular matching.
\item Repeatedly apply the previous step, ignoring all points that are already the endpoint of some half-circle. In particular, recursively identify available white points where the nearest available point on their right is a black point, and then connect that ``adjacent" pair via a half-circle. Continue to split all half-circles that ``wrap around" into an outgoing and incoming strand.
\item When all white points have been used, make each remaining black point the external terminus of a cross-cut. The result is an element of $A^g$.
\end{enumerate}
See Figure \ref{fig:sub-matching_example} for an example of the procedure outlined above. If $g$ has order $d$ in $\Z_{2n+k}$, it follows that $| A^g | = \binom{(2n+k)/d}{n/d}$ whenever $d \mid n$ and $d \mid k$, whereas $| A^g | = 0$ when either $d \nmid n$ or $d \nmid k$.
If $q \mid N$, basic number theory ensures that there are precisely $\varphi(q)$ elements $i \in \Z_N$ with $\gcd(i,N) = N/q$. As the order of $i$ in $\Z_N$ is $N/(i,N)$, there exist precisely $\varphi(q)$ elements $i \in \Z_N$ with order $| i | = q$. Letting $N = 2n+k$, this ensures that there are precisely $\varphi(d)$ elements $g \in \Z_{2n+k}$ such that $| A^g | = \binom{(2n+k)/d}{n/d}$, thus deriving the summation of the theorem.
\end{proof}
\begin{figure}[ht!]
\centering
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,inner sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node[inner sep=0pt] (right) at (8.5,0) {};
\draw[thick] (left) to (right);
\node[fill=white,draw,inner sep=1.8pt] (1) at (1,0) {};
\node[fill=black,draw,inner sep=1.8pt] (2) at (2,0) {};
\node[fill=black,draw,inner sep=1.8pt] (3) at (3,0) {};
\node[fill=black,draw,inner sep=1.8pt] (4) at (4,0) {};
\node[fill=black,draw,inner sep=1.8pt] (5) at (5,0) {};
\node[fill=white,draw,inner sep=1.8pt] (6) at (6,0) {};
\node[fill=white,draw,inner sep=1.8pt] (7) at (7,0) {};
\node[fill=black,draw,inner sep=1.8pt] (8) at (8,0) {};
\end{tikzpicture}
\hspace{0.1in}
\scalebox{2.5}{\raisebox{2pt}{$\Rightarrow$}}
\hspace{0.1in}
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,inner sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node[inner sep=0pt] (right) at (8.5,0) {};
\draw[thick] (left) to (right);
\draw[thick] (2,0) arc (0:180:.5);
\draw[thick] (8,0) arc (0:180:.5);
\draw[thick] (6,0) arc (180:90:2.2);
\draw[thick] (3,0) arc (0:90:2.2);
\node[fill=white,draw,inner sep=1.8pt] (1) at (1,0) {};
\node[fill=black,draw,inner sep=1.8pt] (2) at (2,0) {};
\node[fill=black,draw,inner sep=1.8pt] (3) at (3,0) {};
\node[fill=black,draw,inner sep=1.8pt] (4) at (4,0) {};
\node[fill=black,draw,inner sep=1.8pt] (5) at (5,0) {};
\node[fill=white,draw,inner sep=1.8pt] (6) at (6,0) {};
\node[fill=white,draw,inner sep=1.8pt] (7) at (7,0) {};
\node[fill=black,draw,inner sep=1.8pt] (8) at (8,0) {};
\end{tikzpicture}
\hspace{0.1in}
\scalebox{2.5}{\raisebox{2pt}{$\Rightarrow$}}
\hspace{0.1in}
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,inner sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node[inner sep=0pt] (right) at (8.5,0) {};
\draw[thick] (left) to (right);
\draw[thick] (2,0) arc (0:180:.5);
\draw[thick] (8,0) arc (0:180:.5);
\draw[thick] (6,0) arc (180:90:2.2);
\draw[thick] (3,0) arc (0:90:2.2);
\draw[thick] (4,0) to (4,2);
\draw[thick] (5,0) to (5,2);
\node[fill=white,draw,inner sep=1.8pt] (1) at (1,0) {};
\node[fill=black,draw,inner sep=1.8pt] (2) at (2,0) {};
\node[fill=black,draw,inner sep=1.8pt] (3) at (3,0) {};
\node[fill=black,draw,inner sep=1.8pt] (4) at (4,0) {};
\node[fill=black,draw,inner sep=1.8pt] (5) at (5,0) {};
\node[fill=white,draw,inner sep=1.8pt] (6) at (6,0) {};
\node[fill=white,draw,inner sep=1.8pt] (7) at (7,0) {};
\node[fill=black,draw,inner sep=1.8pt] (8) at (8,0) {};
\end{tikzpicture}
\caption{For every choice of $n$ left-endpoints (white circles) from a set of $2n+k$ points there is a unique annular sub-matching with $n$ half-circles and $k$ cross-cuts. Here the piece of the external boundary corresponding to one sub-matching is drawn as the $x$-axis.}
\label{fig:sub-matching_example}
\end{figure}
Table \ref{tab:Annk(2n+k,k)} of Appendix \ref{sec:appendix_tables} exhibits values of $| \Ann_k(2n+k,k)\, |$ for $0 \leq n,k \leq 10$, all calculated in Maple via the equation of Theorem \ref{thm:maximal_cross-cut_direct_enumeration}. An examination of that table places $| \Ann_k(2n+k,k)\, |$ into direct correspondence with the $T(n+k,n)$ entry of OEIS \seqnum{A241926}. Using Proposition \ref{thm:reflection_equivalence} when necessary to ensure that $2n+k > n$, $| \Ann_k(2n+k,k)\, |$ may also be identified with the ``circular binomial coefficient" $T(2n+k,n)$ of OEIS \seqnum{A047996}. Both of those OEIS sequence reveal a bijection between the $\Ann_k(2n+k,k)$ and binary combinatorial necklaces, a fact that will be formalized in Theorem \ref{thm:annular_matchings_=_necklaces}. Note that a summation equivalent to the one of Theorem \ref{thm:maximal_cross-cut_direct_enumeration} has already been shown to equal the number of binary combinatorial necklaces of certain types \cite{Elash}, and that another proof of the result from Theorem \ref{thm:maximal_cross-cut_direct_enumeration} was given by Sloane \cite{Sloane}.
Before investigating how these results directly relate to annular non-crossing matchings, we observe that the formula of Theorem \ref{thm:maximal_cross-cut_direct_enumeration} may be significantly simplified when $k$ is prime.
\begin{corollary}
\label{thm:maximal_cross-cut_direction_enumeration,_prime_k}
Let $p$ be a prime integer and let $n$ be any non-negative integer. Then
$$| \Ann_p(2n+p,p)\, | = \displaystyle{\frac{1}{2n+p} \binom{2n+p}{n} + \frac{p-1}{p} \ C_{n/p}},$$
where $C_{n/p}$ is the $(n/p)$-th Catalan number if $n/p$ is an integer, and is zero otherwise.
\end{corollary}
\begin{proof}
It is a straightforward exercise to calculate that $\gcd(2n+p,n) = 1$ when $\gcd(p,n)=1$, as well as that $\gcd(2n+p,n) = p$ when $\gcd(p,n) = p$. Theorem \ref{thm:maximal_cross-cut_direct_enumeration} then gives
$$
| \Ann_p(2n+p,n)\, | =
\begin{cases}
\frac{1}{2n+p} \binom{2n+p}{n}, & \text{ when } p \nmid n;\\[1em]
\frac{1}{2n+p} \binom{2n+p}{n} \ + \ \frac{1}{2n+p}(p-1) \binom{(2n+p)/p}{n/p}, & \text{ when } p \mid n.
\end{cases}
$$
A simplification of the final term in the second case yields the desired formula.
\end{proof}
Notice that the more straightforward formula for $| \Ann_k(2n+k,n)\, |$ in Corollary \ref{thm:maximal_cross-cut_direction_enumeration,_prime_k} simplifies to the sequences OEIS \seqnum{A007595} when $k=2$ and OEIS \seqnum{A003441} when $k=3$.
Motivated
by sequences \seqnum{A241926} and \seqnum{A047996}, we now work to develop an explicit bijection between the $| \Ann_k(2n+k,k)\, |$ and binary combinatorial necklaces, providing a new combinatorial identity that supplements the one given by Elashvili, Jibladze and Pataraia \cite{Elash}. A $k$-ary combinatorial necklace is a circular arrangement of ``beads" of up to $k$ distinguishable varieties (typically referred to as ``colors"), such that rotations of the beads around the circle are considered equivalent. Necklaces that are related only via (orientation-reversing) reflection are not considered equivalent. The number of distinct $k$-ary combinatorial necklace with precisely $n$ total beads is denoted by $N_k(n)$. Combinatorial necklaces are well-studied in the literature, and different classes of combinatorial necklaces are the focus of many integer sequences \cite{OEIS}.
In this paper we deal only with binary ($2$-ary) combinatorial necklaces, whose colors we refer to as ``black" and ``white". Our results require increased specificity in that we need to designate the number of beads of each color, so we denote the number of distinct binary necklaces with precisely $n_1$ black beads and precisely $n_2$ white beads by $N_2(n_1,n_2)$. Some places in the literature refer to such combinatorial necklaces as ``binary necklaces of weight $n_1$".
\begin{theorem}
\label{thm:annular_matchings_=_necklaces}
Let $n$ and $k$ be non-negative integers. Then $| \Ann_k(2n+k,k)\, | = N_2(n+k,n)$.
\end{theorem}
\begin{proof}
Denote the set of all combinatorial necklaces with $n_1 = n+k$ black beads and $n_2 = n$ white beads by $S$. We define a function $\phi: \Ann_k(2n+k,k) \rightarrow S$ and show it is bijective. We define $\phi$ by placing white beads at the left-endpoints of exterior half-circles and black beads at right-endpoints of exterior half-circles as well as at the exterior endpoints of cross-cuts. An example of this procedure is shown below.
\begin{center}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick, bend left=70] (210:1) to (240:1);
\draw[thick] (270:1) to (270:.35);
\draw[thick] (180:1) to (180:.35);
\draw[thick, bend right=70] (150:1) to (120:1);
\draw[thick, bend right=20] (300:1) to (90:1);
\draw[thick, bend right=20] (30:1) to (0:1);
\draw[thick] (60:1) to (330:1);
\end{tikzpicture}
\hspace{0.2in}
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{0.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick, bend left=90] (210:1) to (240:1);
\draw[thick] (270:1) to (270:.35);
\draw[thick] (180:1) to (180:.35);
\draw[thick, bend right=90] (150:1) to (120:1);
\draw[thick, bend right=20] (300:1) to (90:1);
\draw[thick, bend right=40] (30:1) to (0:1);
\draw[thick] (60:1) to (330:1);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\hspace{0.2in}
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{0.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\end{center}
The map $\phi$ is clearly injective. To show that $\phi$ is surjective, take any combinatorial necklace $x \in S$. The (unique) annular matching in the inverse image of $\phi^{-1}(x)$ may be recovered via the procedure below.
\begin{enumerate}
\item Begin at any point along the necklace $x$, and proceed in a counter-clockwise direction. Every time we meet a black bead that is immediately counter-clockwise of a white bead, add an external half-circle who right-endpoint is the given black bead and whose left-endpoint is the previous white bead.
\item Continue in a clockwise direction around $x$, repeatedly applying the previous step with the exception that we now ignore beads that are already the endpoint of a half-circle (so we look to identify black beads that are the first available beads in the counter-clockwise direction from an available white bead).
\item When all white beads have been used, add the inner boundary of the annulus. For every black bead that is not already the right-endpoint of a half-circle, add a cross-cut whose exterior endpoint is that black bead.
\end{enumerate}
An example of this inverse procedure is shown below. Notice that the excess of $(n+k) - n = k$ black beads in the inverse procedure yields precisely $k$ cross-cuts, as required. As the rotational notion of equivalence is identical for combinatorial necklaces and annular non-crossing matchings, $\phi$ is a bijection and the result follows.
\begin{center}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\hspace{0.2in}
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{0.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw[thick, bend left=90] (210:1) to (240:1);
\draw[thick, bend right=90] (150:1) to (120:1);
\draw[thick, bend right=40] (30:1) to (0:1);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\hspace{0.2in}
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{0.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw[thick, bend left=90] (210:1) to (240:1);
\draw[thick, bend right=90] (150:1) to (120:1);
\draw[thick, bend right=40] (30:1) to (0:1);
\draw[thick] (60:1) to (330:1);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}\\
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw[thick, bend left=90] (210:1) to (240:1);
\draw[thick, bend right=90] (150:1) to (120:1);
\draw[thick, bend right=20] (300:1) to (90:1);
\draw[thick, bend right=40] (30:1) to (0:1);
\draw[thick] (60:1) to (330:1);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\hspace{.2in}
\scalebox{2.5}{\raisebox{10pt}{$\Rightarrow$}}
\hspace{.2in}
\begin{tikzpicture}
[scale=1.1,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (.35cm);
\draw (0,0) circle (1cm);
\draw[thick, bend left=90] (210:1) to (240:1);
\draw[thick] (270:1) to (270:.35);
\draw[thick] (180:1) to (180:.35);
\draw[thick, bend right=90] (150:1) to (120:1);
\draw[thick, bend right=20] (300:1) to (90:1);
\draw[thick, bend right=40] (30:1) to (0:1);
\draw[thick] (60:1) to (330:1);
\node[draw,fill=black,inner sep=2.5pt] (1c) at (60:1) {};
\node[draw,fill=black,inner sep=2.5pt] (2c) at (30:1) {};
\node[draw,fill=white,inner sep=2.5pt] (3c) at (0:1) {};
\node[draw,fill=white,inner sep=2.5pt] (4c) at (330:1) {};
\node[draw,fill=white,inner sep=2.5pt](5c) at (300:1) {};
\node[draw,fill=black,inner sep=2.5pt](6c) at (270:1) {};
\node[draw,fill=black,inner sep=2.5pt] (7c) at (240:1) {};
\node[draw,fill=white,inner sep=2.5pt] (8c) at (210:1) {};
\node[draw,fill=black,inner sep=2.5pt] (9c) at (180:1) {};
\node[draw,fill=black,inner sep=2.5pt] (10c) at (150:1) {};
\node[draw,fill=white,inner sep=2.5pt] (11c) at (120:1) {};
\node[draw,fill=black,inner sep=2.5pt] (12c) at (90:1) {};
\end{tikzpicture}
\end{center}
\end{proof}
\subsection{Enumeration of annular matchings, general case}
\label{subsec:enumeration_general}
We are finally ready for the enumeration of general $\Ann_k(2n+k,2m+k)$ that do not correspond to the special $m=0$ case of Subsection \ref{subsec:m=0_enumeration_and_necklaces}. There are actually two sub-cases here depending upon whether or not $k$ is nonzero.
\begin{theorem}
\label{thm:general_enumeration}
Let $n$, $m$ , and $k$ be non-negative integers. Then
$$
| \Ann_k(2n+k,2m+k)\, | =
\begin{cases}
| \Ann_0(2n,0)\, | \cdot | \Ann_0(2m,0)\, |, & \text{if \ }k = 0;\\[1em]
\displaystyle{\frac{k}{(2n+k)(2m+k)} \sum_{d | \gcd(k,n,m)} \kern-16pt \varphi(d) \binom{(2n+k)/d}{n/d} \binom{(2m+k)/d}{m/d}}, & \text{if \ } k > 0;
\end{cases}
$$
where $\varphi(d)$ is Euler's totient function.
\end{theorem}
\begin{proof}
Case \#1 follows directly from Proposition \ref{thm:splitting_into_one-sided_product} and Theorem \ref{thm:maximal_cross-cut_direct_enumeration}. For Case \#2 we apply Burnside's lemma by defining an action of $\Z_{(2n+k)(2m+k)}$ on a set $A$ of all non-crossing matchings with $2n+k$ external endpoints and $2m+k$ internal endpoints, prior to any notion of equivalence.
So fix $n,m \geq 0$, $k >0$, and consider annular non-crossing matchings with precisely $n$ exterior half-circles, $m$ interior half-circles, and $k$ cross-cuts. To form our set $A$, we require that the $2n+k$ exterior endpoints are located at $\frac{2\pi}{2n+k}$ radian intervals about the exterior boundary, and that the $2m+k$ interior endpoints are located at $\frac{2\pi}{2m+k}$ radian intervals about the interior boundary. Unlike in the proof of Theorem \ref{thm:maximal_cross-cut_direct_enumeration}, we do not require that the $k$ cross-cuts appear as straight lines that meet the boundaries at right angles, as that condition could require the re-spacing of endpoints on one of the boundary components. Here we consider cross-cuts up to isotopy that fix their endpoints. Absolutely no rotational isotopy of endpoints or rotation of either boundary component is allowed. Notice that $A$ is composed of exactly $k \binom{2n+k}{n} \binom{2m+k}{m}$ matchings. Here the binomial coefficients are derived from specifying which of the endpoints on the inner and outer boundary component correspond to the left-endpoints of half-circles (as in the proofs of Theorems \ref{thm:maximal_cross-cut_direct_enumeration} and \ref{thm:annular_matchings_=_necklaces}), while the additional $k$ term results from the ambiguity in matching up the remaining $k$ endpoints on each side to form $k$ cross-cuts. Notice that specifying both endpoints of a single cross-cut determines how all remaining cross-cuts are matched amongst the remaining $(k-1)$ endpoints on each side.
We then define a left action of $\Z_{(2n+k)(2m+k)}$ on $A$ where $g \cdot a$ is a counter-clockwise rotation of the entire matching by $\frac{2 \pi g}{(2n+k)(2m+k)}$ radians. If the order of $g$ in $\Z_{(2n+k)(2m+k)}$ is $d$, the elements of $A^g$ are matchings that may be radially divided in $d$ identical sub-matchings along both the inner and outer boundaries, with analogous identifications of cross-cuts in each sub-matching. Observe that we do not require that both endpoints of each cross-cut lie in the same sub-matching, merely that each sub-matching exhibits an identical pattern with regards to any cross-cuts involved. If the order of $A^g$ is to be nonzero, it is immediate that we must have both $d \mid (2n+k)$ and $d \mid (2m+k)$. To ensure that left-endpoints of half-circles are mapped to left-endpoints and that cross-cuts are mapped to cross-cuts, it is also required that $d \mid n$, $d \mid m$, and $d \mid k$. It is obvious that $d \mid \gcd(k,n,m)$ is necessary and sufficient to satisfy all of these conditions. Thus the order of $A^g$ is nonzero if and only if $d \mid \gcd(k,n,m)$.
So take $g \in \Z_{(2n+k)(2m+k)}$, where $g$ has order $d$ in $\Z_{(2n+k)(2m+k)}$ and we assume that $d \mid \gcd(k,n,m)$. There are $\binom{2n+k}{n}$ choices of how to arrange the outer boundary of each sub-matching and $\binom{2m+k}{m}$ independent choices for the inner boundary of each sub-matching. After the endpoints belonging to cross-cuts have been identified, there are also $k$ independent choices for how the cross-cuts match up across the annulus. These $k$ choices correspond to similarly-symmetrical matchings whose blocks are identical apart from the fact that their cross-cuts uniformly ``twist around" the annulus by different amounts. We may conclude that $| A^g | = k \binom{(2n+k)/d}{n/d} \binom{(2m+k)/d}{m/d}$ if $d \mid \gcd(k,n,m)$.
Similarly to our argument from the proof of Theorem \ref{thm:maximal_cross-cut_direct_enumeration}, if $q \mid (2n+k)(2m+k)$ one may show that there are precisely $\varphi(q)$ elements $i \in \Z_{(2n+k)(2m+k)}$ with order $| i | = q$. It follows that there are precisely $\varphi(d)$ elements $g \in \Z_{(2m+k)(2n+k)}$ with $| A^g | = k \binom{(2n+k)/d}{n/d} \binom{(2m+k)/d}{m/d}$, yielding the equation of Case \#2 via an application of Burnside's lemma.
\end{proof}
Theorems \ref{thm:maximal_cross-cut_direct_enumeration} and \ref{thm:general_enumeration} combine to provide a closed formula for every $| \Ann_k(2n+k,2m+k)\, |$ where $m,n,k$ are any choice of non-negative integers. This allows us to directly enumerate $\Ann(n,m) = \bigcup_k \Ann_k(n,m)$ for all $n,m \geq 0$.
Table \ref{tab:Ann(n,m)} of Appendix \ref{sec:appendix_tables} presents values of $| \Ann(n,m)\, |$ for all $0 \leq n,m \leq 12$, calculated in Maple using the equations of Theorems \ref{thm:maximal_cross-cut_direct_enumeration} and \ref{thm:general_enumeration}. In Proposition \ref{thm:graph_interpretation,_no_crosscuts}, we have already established that the $n=0$ row (or $m=0$ column) of Table \ref{tab:Ann(n,m)} corresponds to OEIS \seqnum{A003239}. Also noted in Section \ref{sec:basic_annular_results} what the fact that the $n=1$ row (or $m=1$ column) of Table \ref{tab:Ann(n,m)} corresponds to the Catalan numbers. However, no other rows, diagonals, or triangles of numbers from Table \ref{tab:Ann(n,m)} appear to correspond to any known sequences on OEIS \cite{OEIS}. This yields an entire family of new integer sequences with an explicit geometric interpretation. Of particular interest are the rows for $n>2$, representing new generalizations of the Catalan numbers that appear as later terms in a sequence of sequences beginning with OEIS \seqnum{A003239} and the Catalan numbers.
Table \ref{tab:Ann(2n)} of Appendix \ref{sec:appendix_tables} shows values of $\Ann(2n)$ for small values of $n$. These values are most easily derived by summing over the anti-diagonals from Table \ref{tab:Ann(n,m)}. The sequence of Table \ref{tab:Ann(2n)} also fails to appear as a known integer sequence on OEIS \cite{OEIS}.
\section{Future directions}
Our success in determining closed formulas for the $| \Ann(n,m)\, |$ invites generalizations of non-crossing matchings to even more complicated subsets of the real plane. One possibility is the enumeration of non-crossing matchings in a plane with $n$ circular ``holes".
Immediately notice that the one hole case will yield enumerations identical to the circular non-crossing matchings of Goldbach and Tijdeman \cite{GT}, as those two classes of matchings may be related via ``reflection" across the single boundary circle. However, the $n$ hole case should yield a new collection of enumerations for all $n \geq 2$. In particular, the $n=2$ hole case should give enumerations that are distinct from the annular non-crossing matchings of this paper. As we are dealing with subsets of $\R^2$ (as opposed to subsets of the $2$-sphere, where the twice-punctured plane and the annulus are topologically equivalent), any enumeration of non-crossing matchings in the two hole case will need to account for both cross-cuts and ``wrap-arounds". Here we use ``wrap-arounds" to refer to half-circles that, despite having both endpoints on one boundary component, fully enclose the second boundary component. An even more complex consideration of various cross-cuts ``wrap-arounds" would be required for the $n$ hole case when $n>2$.
\section{Acknowledgments}
Both authors would like to thank the Department of Mathematics \& Statistics at Valparaiso University, whose MATH 492 Research in Mathematics course provided the framework under which this research took place. The first author would also like to thank Dr.~Lara Pudwell, who offered helpful advice in the latter stages of the project.
\appendix
\section{Tables of values}
\label{sec:appendix_tables}
All tables in this appendix were generated in Maple 18 using Theorems \ref{thm:maximal_cross-cut_direct_enumeration} and \ref{thm:general_enumeration}. Coding is available upon request from Paul Drube ({\tt paul.drube@valpo.edu}).
\begin{table}[h!]
\centering
\begin{small}
\begin{tabular}{>{$}c<{$}|>{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} }
n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 \\
3 & 4 & 5 & 7 & 10 & 12 & 15 & 19 & 22 & 26 & 31 & 35 \\
4 & 10 & 14 & 22 & 30 & 43 & 55 & 73 & 91 & 116 & 140 & 172 \\
5 & 26 & 42 & 66 & 99 & 143 & 201 & 273 & 364 & 476 & 612 & 776 \\
6 & 80 & 132 & 217 & 335 & 504 & 728 & 1038 & 1428 & 1944 & 2586 & 3399 \\
7 & 246 & 429 & 715 & 1144 & 1768 & 2652 & 3876 & 5538 & 7752 & 10659 & 14421 \\
8 & 810 & 1430 & 2438 & 3978 & 6310 & 9690 & 14550 & 21318 & 30667 & 43263 & 60115 \\
9 & 2704 & 4862 & 8398 & 14000 & 22610 & 35530 & 54484 & 81719 & 120175 & 173593 & 246675 \\
10 & 9252 & 16796 & 29414 & 49742 & 81752 & 130752 & 204347 & 312455 & 468754 & 690690 & 1001603
\end{tabular}
\end{small}
\caption{Enumeration of $| \Ann_k(2n+k,k)\, |$.}
\label{tab:Annk(2n+k,k)}
\end{table}
\begin{table}[h!]
\centering
\begin{small}
\begin{tabular}{>{$}c<{$}|>{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$}}
n/m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline
0 & \textbf{1} & & 1 & & 2 & & 4 & & 10 & & 26 & & 80 \\
1 & & \textbf{1} & & 1 & & 2 & & 5 & & 14 & & 42 & \\
2 & 1 & & \textbf{2} & & 3 & & 7 & & 17 & & 48 & & 146 \\
3 & & 1 & & \textbf{2} & & 3 & & 8 & & 24 & & 72 & \\
4 & 2 & & 3 & & \textbf{7} & & 14 & & 38 & & 106 & & 335 \\
5 & & 2 & & 3 & & \textbf{8} & & 20 & & 60 & & 189 & \\
6 & 4 & & 7 & & 14 & & \textbf{34} & & 90 & & 263 & & 834 \\
7 & & 5 & & 8 & & 20 & & \textbf{58} & & 175 & & 560 & \\
8 & 10 & & 17 & & 38 & & 90 & & \textbf{255} & & 750 & & 2420 \\
9 & & 14 & & 24 & & 60 & & 175 & & \textbf{546} & & 1764 & \\
10 & 26 & & 48 & & 106 & & 263 & & 750 & & \textbf{2268} & & 7372 \\
11 & & 42 & & 72 & & 189 & & 560 & & 1764 & & \textbf{5774} & \\
12 & 80 & & 146 & & 335 & & 834 & & 2420 & & 7372 & & \textbf{24198}
\end{tabular}
\end{small}
\caption{Enumeration of $| \Ann(n,m)\, |$. Entries where $| \Ann(n,m)\, | =0$ have been left blank, and $| \Ann(n,n)\, |$ is bolded to emphasize $n \leftrightarrow m$ symmetry.}
\label{tab:Ann(n,m)}
\end{table}
\begin{table}[h!]
\centering
\scalebox{.9}{
\begin{tabular}{>{$}c<{$}|>{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$}}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline
| \Ann(2n)\, | & 1 & 3 & 8 & 20 & 57 & 166 & 538 & 1762 & 6045 & 21040 & 74628 & 267598 & 970134 & 3544416
\end{tabular}}
\caption{Enumeration of $| \Ann(2n)\, |$.}
\label{tab:Ann(2n)}
\end{table}
\begin{thebibliography}{1}
\bibitem{GT} R. W. Goldbach and R. Tijdeman, Pairings of 2n points on a
circle, \emph{Utilitas Math.} \textbf{38} (1990), 277--284.
\bibitem{Elash} A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and ``Hermite reciprocity", \emph{J. Algebraic Combin.} \textbf{10} (1999), 173--188.
\bibitem{Harary} F. Harary and E. M. Palmer, \emph{Graphical Enumeration},
Academic Press, 1973.
\bibitem{Sloane} N. J. A. Sloane, A note on modular partitions and necklaces,
May 6 2014, available at \\ \url{http://oeis.org/A047996/a047996.pdf}.
\bibitem{Stanley} R. P. Stanley, \emph{Catalan Numbers},
Cambridge University Press, 2015.
\bibitem{Stanley1} R. P. Stanley, \emph{Enumerative Combinatorics},
Vol.~1, Cambridge University Press, 2011.
\bibitem{Stanley2} R. P. Stanley, \emph{Enumerative Combinatorics}, Vol.~2,
Cambridge University Press, 1999.
\bibitem{OEIS} N. J. A. Sloane, The Encyclopedia of Integer Sequences.
Available at \url{http://oeis.org}, 2011.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A19; Secondary 05C30.
\noindent \emph{Keywords: }
non-crossing matching, combinatorial necklace, Catalan number.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A002995},
\seqnum{A003239},
\seqnum{A003441},
\seqnum{A007595},
\seqnum{A047996}, and
\seqnum{A241926}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 7 2015;
revised versions received December 15 2015; December 18 2015.
Published in {\it Journal of Integer Sequences}, January 10 2016.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}