Annular Non-Crossing Matchings

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

                 Paul.Drube@valpo.edu
           Puttipong.Pongtanapaisan@valpo.edu

Abstract

It is well known that the number of distinct non-crossing matchings of n halfcircles 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 ≥ 0.

1 Introduction

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 1. 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 [5].

⇔

Figure 1: The bijection between linear non-crossing matchings and ordered rooted trees.

Non-crossing matchings admit many interesting generalizations if one restricts curves to a subset of ℝ^{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 C̃_{n}.

One in-depth study of circular non-crossing matchings was undertaken by Goldbach and Tijdeman [1]. In that work, an involved application of Burnside’s lemma showed that:

C̃_{n} = \frac{1}{2n} (∑_{d|n} φ(n/d)\binom{2d}{d}) − \frac{1}{2}C_{n} + \frac{1}{2}C_{(n−1)/2},  (1)

where φ(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 (1), 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 2. Notice that this correspondence identifies C̃_{n} with the (n−1)^{st} entry of OEIS \underline{A002995}. See Harary and Palmer [3] for further discussion of the graphtheoretic interpretations of C̃_{n}.

⇔

Figure 2: The bijection between circular non-crossing matchings and unrooted planar trees.

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 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) = {M ∈ Ann(n, m) | n + m = N} and Ann(N) ≠ 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 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) = ⋃_{k} Ann_{k}(n, m). See Figure 3 for several quick examples.

Figure 3: An element of Ann_{2}(6, 4), and an element of Ann_{0}(6, 0).

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

1.1 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 2 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 5, Theorem 8).

Section 3 presents our enumerative results. Subsection 3.1 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 9.

Theorem 1. Let n and k be non-negative integers. Then

| Ann_{k}(2n + k, k) | = \begin{cases}1, & if n = k = 0; \\ \frac{1}{2n + k} ∑_{d| gcd(k,n)}φ(d)\binom{(2n + k)/d}{n/d}, & otherwise; \end{cases}

where φ(d) is Euler’s totient function.

Subsection 9 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 11 will prove the following statement.

Theorem 2. Let n and k be non-negative integers. Then | Ann_{k}(2n + k, k) | = N_{2}(n + k, n).

Our results for | Ann_{k}(2n+k, k) | are then used in Subsection 3.2 to enumerate | Ann_{k}(2n+ k, 2m + k)| for the remaining choices of n, m, and k. In particular, Theorem 12 will prove the result below.

Theorem 3. Let n, m, k be non-negative integers. Then

| Ann_{k}(2n+k, 2m+k) | = \begin{cases}| Ann_{0}(2n, 0)| · | Ann_{0}(2m, 0)|, & if k = 0; \\ \frac{k}{(2n + k)(2m + k)} ∑_{d| gcd(k,n,m)} φ(d)\binom{(2n + k)/d}{n/d}\binom{(2m + k)/d}{m/d}, & if k > 0; \end{cases}

where φ(d) is Euler’s totient function.

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 9 and 12.

2 Basic results about annular non-crossing matchings

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 3. 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 C̃_{n}.

Proposition 4. Let n, m be non-negative integers. Then | Ann_{k}(n, m) | = | Ann_{k}(m, n) | for all k ≥ 0. In particular, | Ann(n, m) | = | Ann(m, n) | for all n, m ≥ 0.

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 ≥ 0.

The primary use of Proposition 4 is that it will allow us to restrict our attention to Ann(n, m) and Ann_{k}(n, m) such that n ≥ m. Yet even within the realm where n ≥ 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.

Proposition 5. 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.

Proof. The required bijection is analogous to the constructions of Figures 1 and 2 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:

⇔

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.

Notice that the class of planar graphs from Proposition 5 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 5 does identify | Ann(2n, 0) | with the n^{th} entry of OEIS \underline{A003239}. See Harary and Palmer [3] or Stanley [7] for further bijections involving | Ann(2n, 0) |.

Via the planar graph bijections of Section 1 and Proposition 5, it is immediate that C̃_{n} ≤ | Ann(2n, 0) | ≤ C_{n} for all n ≥ 0. One can easily verify that 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 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.

Proposition 6. For all n ≥ 3 we have C̃_{n} < | Ann(2n, 0) | < C_{n}.

Proof. We define a map ϕ 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 ψ 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.

ϕ( A ) =  A  ψ(  A ) =  A

Both ϕ and ψ are clearly well-defined and surjective for all n ≥ 0. To see that neither map is injective, we construct a counterexample to injectivity that simultaneously holds for all n ≥ 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 ϕ, while the (distinct) annular non-crossing matchings on the right of the subsequent image map to the same circular non-crossing matching via ψ.

ϕ( A  ) = ϕ(  A )  ψ(  A ) = ψ(  A )

With the zero cross-cuts case well-understood, we expand our attention to Ann_{k}(n, m) with k ≥ 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 maximal crosscut 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 4, 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 ±∞.

A  ⇔  A

Figure 4: The bijection between Ann_{1}(2n + 1, 1) and linear non-crossing matchings of order n.

Maximal cross-cut annular matchings will be directly enumerated in Subsection 3.1 for all k ≥ 0, and those enumerations will be necessary building blocks for the general enumerations of Subsection 3.2. 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.

Proposition 7. 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) | · | Ann_{k}(2m + k, k) |

Proof. We define a general map ϕ : Ann_{k}(2n+k, 2m+k) → Ann_{k}(2n+k, k)⊕Ann_{k}(k, 2m+k) that becomes a bijection when m = 0 or k = 0. This ϕ is defined by deleting internal halfcircles in the first coordinate of the output and deleting external half-circles in the second coordinate, as in the example below.

↦ (  ,  )

This map ϕ is clearly a bijection whenever m = 0. To see that ϕ 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”.

It can be shown that the equality of Proposition 7 holds precisely when n = 0 or m = 0 or k < 2. If k ≥ 2, n ≥ 1, and m ≥ 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 3, motivating our omission of the more general result.

For our final result of this section, we adapt the planar graph bijection of Proposition 5 to the general case of Ann_{k}(2n + k, 2m + k). Although the resulting language of Theorem 8 is arguably rather contrived, it combines with Proposition 5 to give a succinct geometric characterization of any class of annular matchings with at least one cross-cut.

Theorem 8. Let n, m, k be non-negative integers and let k ≥ 1. Then | Ann_{k}(2n+k, 2m+k) | equals the number of connected planar graphs such that:

1. The only cycle in the graph is a single k-cycle.

2. There are n edges within the area bounded by the cycle.

3. There are m edges outside the area bounded by the cycle.

Proof. The methodology used is extremely similar to what has already been presented in Proposition 5. Notice that a collection of k cross-cuts produces a single k-cycle, as shown below.

⇔

Any internal half-circles are then counted by edges inside the k-cycle, while external halfcircles are counted by edges outside the k-cycle.

3 Enumeration of annular non-crossing matchings

We are now ready for the general enumerative results that form the core of this paper. Subsection 3.1 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 3.2 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 2, 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.

3.1 Enumeration of maximal cross-cut annular matchings and combinatorial necklaces

Burnside’s lemma has already been mentioned as the method used in Goldbach and Tijdeman [1] 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} = {a ∈ A | ga = a} when ranging over all g ∈ G, that is |A/G| = \frac{1}{|G|} ∑_{g∈G} |A^{g}|.

So fix n, k ≥ 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π}{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 = ℤ_{2n+k} on A whereby g · a is counter-clockwise rotation of a by \frac{2π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:

Theorem 9. Let n and k be non-negative integers. Then

| Ann_{k}(2n + k, k) | = \begin{cases}1, & if n = k = 0; \\ \frac{1}{2n + k} ∑_{d| gcd(k,n)}φ(d)\binom{(2n + k)/d}{n/d}, & otherwise; \end{cases}

where φ(d) is Euler’s totient function.

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 ∑_{g∈ℤ_{2n+k}} |A^{g}| = ∑_{d|(2n+k,n)} φ(d)\binom{(2n+k)/d}{n/d}. So take g ∈ ℤ_{2n+k}, and assume that g has order d in ℤ_{2n+k} Notice that Lagrange’s theorem guarantees d | (2n + k), although it may or may not be true that d | 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 submatchings, 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 ∤ 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 | n and d | k together guarantee that d | (2n + k), making |A^{g}| ≠ 0 a possibility in that case. If d | 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 halfcircles. To explicitly see that |A^{g}| = \binom{(2n+k)/d}{n/d}, we proceed as below.

1. 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).

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

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

4. 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}.

See Figure 5 for an example of the procedure outlined above. If g has order d in ℤ_{2n+k}, it follows that |A^{g}| = \binom{(2n+k)/d}{n/d} whenever d | n and d | k, whereas |A^{g}| = 0 when either d ∤ n or d ∤ k.

If q | N, basic number theory ensures that there are precisely φ(q) elements i ∈ ℤ_{N} with gcd(i, N) = N/q. As the order of i in ℤ_{N} is N/(i, N), there exist precisely φ(q) elements i ∈ ℤ_{N} with order |i| = q. Letting N = 2n + k, this ensures that there are precisely φ(d) elements g ∈ ℤ_{2n+k} such that |A^{g}| = \binom{(2n+k)/d}{n/d}, thus deriving the summation of the theorem.

⇒  ⇒

Figure 5: 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.

Table 1 of Appendix A exhibits values of | Ann_{k}(2n + k, k) | for 0 ≤ n, k ≤ 10, all calculated in Maple via the equation of Theorem 9. An examination of that table places | Ann_{k}(2n + k, k) | into direct correspondence with the T (n + k, n) entry of OEIS \underline{A241926}. Using Proposition 4 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 \underline{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 11. Note that a summation equivalent to the one of Theorem 9 has already been shown to equal the number of binary combinatorial necklaces of certain types [2], and that another proof of the result from Theorem 9 was given by Sloane [4].

Before investigating how these results directly relate to annular non-crossing matchings, we observe that the formula of Theorem 9 may be significantly simplified when k is prime.

Corollary 10. Let p be a prime integer and let n be any non-negative integer. Then

| Ann_{p}(2n + p, p) | = \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.

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 9 then gives

| Ann_{p}(2n + p, n) | = \begin{cases}\frac{1}{2n+p} \binom{2n+p}{n}, & when p ∤ n; \\ \frac{1}{2n+p} \binom{2n+p}{n} + \frac{1}{2n+p}(p − 1)\binom{(2n+p)/p}{n/p}, & when p | n. \end{cases}

A simplification of the final term in the second case yields the desired formula.

Notice that the more straightforward formula for | Ann_{k}(2n + k, n) | in Corollary 10 simplifies to the sequences OEIS \underline{A007595} when k = 2 and OEIS \underline{A003441} when k = 3.

Motivated by sequences \underline{A241926} and \underline{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 [2]. 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 [8].

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}”.

Theorem 11. Let n and k be non-negative integers. Then | Ann_{k}(2n+k, k) | = N_{2}(n+k, n).

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 ϕ : Ann_{k}(2n+k, k) → S and show it is bijective. We define ϕ 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.

⇒  ⇒

The map ϕ is clearly injective. To show that ϕ is surjective, take any combinatorial necklace x ∈ S. The (unique) annular matching in the inverse image of ϕ^{−1}(x) may be recovered via the procedure below.

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

2. 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 counterclockwise direction from an available white bead).

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

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, ϕ is a bijection and the result follows.

⇒  ⇒

⇒  ⇒

3.2 Enumeration of annular matchings, general case

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 3.1. There are actually two sub-cases here depending upon whether or not k is nonzero.

Theorem 12. Let n, m , and k be non-negative integers. Then

| Ann_{k}(2n+k, 2m+k) | = \begin{cases}| Ann_{0}(2n, 0) | · | Ann_{0}(2m, 0) |, & if k = 0; \\ \frac{k}{(2n + k)(2m + k)} ∑_{d| gcd(k,n,m)} φ(d)\binom{(2n + k)/d}{n/d}\binom{(2m + k)/d}{m/d}, & if k > 0; \end{cases}

where φ(d) is Euler’s totient function.

Proof. Case #1 follows directly from Proposition 7 and Theorem 9. For Case #2 we apply Burnside’s lemma by defining an action of ℤ_{(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 ≥ 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π}{2n+k} radian intervals about the exterior boundary, and that the 2m + k interior endpoints are located at \frac{2π}{2m+k} radian intervals about the interior boundary. Unlike in the proof of Theorem 9, we do not require that the k crosscuts 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 leftendpoints of half-circles (as in the proofs of Theorems 9 and 11), 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 ℤ_{(2n+k)(2m+k)} on A where g · a is a counter-clockwise rotation of the entire matching by \frac{2πg}{(2n+k)(2m+k)} radians. If the order of g in ℤ_{(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 | (2n + k) and d | (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 | n, d | m, and d | k. It is obvious that d | 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 | gcd(k, n, m).

So take g ∈ ℤ_{(2n+k)(2m+k)}, where g has order d in ℤ_{(2n+k)(2m+k)} and we assume that d | 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 | gcd(k, n, m).

Similarly to our argument from the proof of Theorem 9, if q | (2n + k)(2m + k) one may show that there are precisely φ(q) elements i ∈ ℤ_{(2n+k)(2m+k)} with order |i| = q. It follows that there are precisely φ(d) elements g ∈ ℤ_{(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.

Theorems 9 and 12 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) = ⋃_{k} Ann_{k}(n, m) for all n, m ≥ 0.

Table 2 of Appendix A presents values of | Ann(n, m) | for all 0 ≤ n, m ≤ 12, calculated in Maple using the equations of Theorems 9 and 12. In Proposition 5, we have already established that the n = 0 row (or m = 0 column) of Table 2 corresponds to OEIS \underline{A003239}. Also noted in Section 2 what the fact that the n = 1 row (or m = 1 column) of Table 2 corresponds to the Catalan numbers. However, no other rows, diagonals, or triangles of numbers from Table 2 appear to correspond to any known sequences on OEIS [8]. 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 \underline{A003239} and the Catalan numbers.

Table 3 of Appendix A shows values of Ann(2n) for small values of n. These values are most easily derived by summing over the anti-diagonals from Table 2. The sequence of Table 3 also fails to appear as a known integer sequence on OEIS [8].

4 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 [1], 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 ≥ 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 ℝ^{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.

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

A Tables of values

All tables in this appendix were generated in Maple 18 using Theorems 9 and 12. Coding is available upon request from Paul Drube (paul.drube@valpo.edu).

\begin{matrix}n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 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{matrix}

Table 1: Enumeration of | Ann_{k}(2n + k, k) |.

n/m 0 1 2 3 4  5  6  7  8  9  10  11  12
0  1  1  2  4  10  26  80
1  1  1  2  5  14  42
2  1  2  3  7  17  48  146
3  1  2  3  8  24  72
4  2  3  7  14  38  106  335
5  2  3  8  20  60  189
6  4  7  14  34  90  263  834
7  5  8  20  58  175  560
8 10  17  38  90  255  750  2420
9  14  24  60  175  546  1764
10 26  48  106  263  750  2268  7372
11  42  72  189  560  1764  5774
12 80  146  335  834  2420  7372  24198

Table 2: Enumeration of | Ann(n, m) |. Entries where | Ann(n, m) | = 0 have been left blank, and | Ann(n, n) | is bolded to emphasize n ↔ m symmetry.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ | Ann(2n) | & 1 & 3 & 8 & 20 & 57 & 166 & 538 & 1762 & 6045 & 21040 & 74628 & 267598 & 970134 & 3544416 \end{matrix}

Table 3: Enumeration of | Ann(2n) |.

References

[1] R. W. Goldbach and R. Tijdeman, Pairings of 2n points on a circle, Utilitas Math. 38 (1990), 277–284.

[2] A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and “Hermite reciprocity”, J. Algebraic Combin. 10 (1999), 173–188.

[3] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.

[4] N. J. A. Sloane, A note on modular partitions and necklaces, May 6 2014, available at

   http://oeis.org/A047996/a047996.pdf.

[5] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[6] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2011.

[7] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[8] N. J. A. Sloane, The Encyclopedia of Integer Sequences. Available at http://oeis.org, 2011.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05C30. Keywords: non-crossing matching, combinatorial necklace, Catalan number.

(Concerned with sequences \underline{A002995}, \underline{A003239}, \underline{A003441}, \underline{A007595}, \underline{A047996}, and \underline{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.