Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers

Abstract

The d-dimensional Catalan numbers form a well-known sequence of numbers which count balanced bracket expressions over an alphabet of size d. In this paper, we introduce and study what we call d-dimensional prime Catalan numbers, a sequence of numbers which count only a very specific subset of indecomposable balanced bracket expressions. These numbers were encountered during the investigation of what we call trapezoidal diagrams of geometric graphs, such as triangulations or crossing-free perfect matchings. In essence, such a diagram is obtained by augmenting the geometric graph in question with its trapezoidal decomposition, and then forgetting about the precise coordinates of individual vertices while preserving the vertical visibility relations between vertices and segments. We note that trapezoidal diagrams of triangulations are closely related to abstract upward triangulations. We study the numbers of such diagrams in the cases of (i) perfect matchings and (ii) triangulations. We give bijective proofs which establish relations with 3-dimensional (prime) Catalan numbers. This allows us to determine the corresponding exponential growth rates exactly as (i) $5.196^n$ and (ii) $23.459^n$ (bases are rounded to three decimal places). Finally, we give exponential lower bounds for the maximum number of embeddings that a trapezoidal diagram can have on any given point set.

1 Introduction

We begin by introducing the two main notions to be studied in this paper, namely prime Catalan numbers and trapezoidal diagrams. The former is a purely combinatorial concept related to balanced bracket expressions; it is, as such, of independent interest to combinatorialists. The latter is a simple and natural structure which encodes the vertical visibility relations between segments in a geometric graph; it is studied as part of a program towards better bounds on the maximum number of crossing-free geometric graphs.

Prime Catalan Numbers. A balanced bracket expression (of dimension d) is a finite string c over an alphabet $\{b_1,\ldots ,b_d\}$ of d brackets such that all brackets occur in equal numbers in c, and such that every prefix of c contains at least as many occurrences of $b_i$ as of $b_{i+1}$, for $1\le i \le d-1$. The size $m = |c|$ of c is defined as the number of occurrences of $b_1$. As an example, let us enumerate all balanced bracket expressions of dimension $d=3$ (with brackets $b_1 = `\langle$’, $b_2 = `|$’, and $b_3 = `\rangle$’) and of size $m=2$.

$$\begin{aligned} \langle |\langle \rangle |\rangle&\langle \langle ||\rangle \rangle&\langle |\langle |\rangle \rangle&\langle \langle |\rangle |\rangle&\langle |\rangle \langle |\rangle \end{aligned}$$

We call a balanced bracket expression of dimension d prime if it does not contain any non-empty, contiguous and proper substrings that are themselves balanced bracket expressions (of dimension d). Note that in the above enumeration, only the first two expressions are prime, whereas the other three all contain “$\langle |\rangle$” as a proper substring.

The mth d-dimensional Catalan number $C^{(d)}_m$ can be defined as the number of balanced bracket expressions of dimension d and of size m [5, 13]. The most prominent instantiation of this family of sequences is of course given by the customary (2-dimensional) Catalan numbers $C_m = C^{(2)}_m$. These numbers are ubiquitous in enumerative combinatorics, as illustrated by a famous exercise in Stanley’s book with no less than 66 different combinatorial interpretations [12, Ex. 6.19]. In this paper, however, the focus will be on the 3-dimensional case [7]. For easy reference, below we enumerate the first ten entries in the sequence corresponding to $C^{(3)}_m$, starting with $m=0$.

$$\begin{aligned} 1, 1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330,\ldots \end{aligned}$$

Explicit product formulae for the numbers $C^{(d)}_m$ are known and can be obtained by employing the famous hook-length formula for standard Young tableaux of shape $(m^d)$ (see [8] for a precise statement and an insightful proof of the hook-length formula). For example, for dimension $d=3$ we have

$$\begin{aligned} C^{(3)}_m = \frac{2(3m)!}{(m+2)!(m+1)!m!}. \end{aligned}$$

(1)

By employing Stirling’s approximation for factorials, we further get the asymptotic estimate

$$\begin{aligned} C^{(3)}_m \sim \frac{\sqrt{3}}{\pi }\, m^{-4} 27^m \;(\text {as }m \rightarrow \infty ). \end{aligned}$$

(2)

In a similar vein, we denote by $P^{(d)}_m$ the number of balanced bracket expressions of dimension d and of size m which are prime. We call $P^{(d)}_m$ the mth d-dimensional prime Catalan number. In spite of the natural definition, we are not aware of any previous work that studies these numbers or acknowledges their existence. Below we enumerate the first ten entries in the sequence corresponding to $P^{(3)}_m$, starting again with $m=0$.

$$\begin{aligned} 1, 1, 2, 12, 107, 1178, 14805, 203885, 3002973, 46573347, \ldots \end{aligned}$$

This sequence stands in stark contrast to the customary 2-dimensional case. Indeed, by reusing the brackets $b_1 = `\langle$’ and $b_2 = `\rangle$’, we see that the empty string $\varepsilon$ and “$\langle \rangle$” are the only prime balanced bracket expressions of dimension $d=2$. Hence, $P^{(2)}_m = 0$ for $m \ge 2$.

In Sect. 4 we study various aspects of the numbers $P^{(d)}_m$ and we show how to compute them. Theorem 1.1, which will be proved in that last section, gives the rate of exponential growth of the prime Catalan numbers, and it is the only result that is relevant for the earlier sections. In the following, let $C^{(d)}(x) := \sum _{m=0}^\infty C^{(d)}_mx^m$ denote the ordinary generating function of the d-dimensional Catalan numbers.

Theorem 1.1

For any dimension $d \ge 3$, the prime Catalan numbers satisfy

$$\begin{aligned} \lim _{m \rightarrow \infty } \root m \of {P^{(d)}_m} = \gamma _d, \; \text { where } \gamma _d := \left( \frac{d}{C^{(d)}(1/d^d)}\right) ^d. \end{aligned}$$

Decimal approximations of the numbers $\gamma _d$ can be computed automatically using any modern computer algebra system. For $\gamma _3$ we even obtain a closed formula.

$$\begin{aligned} \gamma _3 = \frac{27}{({729\sqrt{3}}/({40\pi }) - 9)^3} \approx 23.45948,&\gamma _4 \approx 251.78874,&\gamma _5 \approx 3119.93434. \end{aligned}$$

(3)

Trapezoidal Diagrams.

Let S be a set of n points in the plane such that no three points are on a common line. Additionally, we assume throughout that all points have distinct x-coordinates, which means that they can be ordered as $s_1,\ldots ,s_n$ from left to right. We then say that a point $s_i$ is to the left of another point $s_j$ if $i < j$ holds.

A crossing-free geometric graph or plane graph (on S) is a graph G with vertex set S such that any two edges, which are drawn as straight-line segments between the corresponding endpoints, do not intersect except possibly at a common endpoint. In this paper we restrict our attention to two special cases of crossing-free geometric graphs, namely perfect matchings (1-regular crossing-free geometric graphs) and triangulations (edge-maximal crossing-free geometric graphs). Even though we tend to omit the adjective crossing-free, all geometric graphs considered in this paper have no crossings.

The trapezoidal decomposition of a geometric graph G is a well-known and useful notion (see [9] for a classic application) which is obtained by drawing a vertical extension upwards and downwards outgoing from each point in S until a segment of G is hit; if there is no obstruction, then the extension is drawn as an infinite ray. If the extension going upwards (downwards) from a point s hits the segment corresponding to an edge e, then we say that e sees s below (above) in G. Clearly, every point can be seen by at most two edges, once below and once above.

We now define the trapezoidal diagram (or, just diagram) of G, where G is either a perfect matching or a triangulation. Informally speaking, the trapezoidal diagram is equivalent to the trapezoidal decomposition except that we discard the coordinates of the vertices.

Definition 1.2

Let n be even, and let M be a perfect matching on S. Then, the trapezoidal diagram of M, denoted by $D_M$, is defined as follows.

• (i) $D_M$ is an abstract graph with vertex set $[n] = \{1,2,\ldots ,n\}$ so that there is an edge $\{i,j\}$ in $D_M$ if and only if there is an edge $\{s_i,s_j\}$ in M.

• (ii) Every edge in $D_M$ has two distinguished sequences with the indices $i_1,\ldots ,i_k$ of the points $s_{i_1},\ldots ,s_{i_k}$ (sorted from left to right) that the corresponding edge in M can see below and above, respectively.

• (iii) There are two additional sequences with the indices of the points (sorted from left to right) that no edge in M can see below and above, respectively.

If there exists an isomorphism $[n] \rightarrow [n]$ between $D_{M_1}$ and $D_{M_2}$ that preserves the structure imposed by (i), (ii) and (iii), then we identify $D_{M_1}$ and $D_{M_2}$, and we say that $M_1$ and $M_2$ have the same trapezoidal diagram.

We will typically not appeal to the above definition directly. Instead, we will argue on the basis of a drawing of a trapezoidal diagram. Incidentally, a drawing of $D_M$ is a plane (i.e., without crossings) drawing of the underlying graph and its trapezoidal decomposition, where we allow edges of the graph to be drawn as arbitrary x-monotone Jordan curves. All orientations of edges must however remain the same (i.e., a left endpoint remains a left endpoint in the drawing) and all vertical visibility relations must remain identical (i.e., the order from left to right in which an edge sees points below does not change, and so on).

Refer to Fig. 1 for interesting examples. Observe that the geometric graph M combined with its trapezoidal decomposition is an instance of a drawing of $D_M$. Further note that two distinct perfect matchings $M_1$ and $M_2$ on the same point set S may have the same trapezoidal diagram.

Fig. 1

On the left, a perfect matching with trapezoidal decomposition and three drawings of its trapezoidal diagram, which are distinguished visually from geometric graphs by leaving vertices blank. On the right, two perfect matchings on the same point set with the same trapezoidal diagram

Let us remark that trapezoidal diagrams of perfect matchings are related to the well studied notion of (directed) bar visibility graphs (see for example [14] for a definition and further references). However, that class of graphs imposes much coarser equivalence classes on the set of collections of non-intersecting segments in the plane.

Definition 1.3

Let $n > 2$ and assume that S has a triangular convex hull with the edge $\{s_1,s_n\}$ on the lower envelope. Then, the trapezoidal diagram of a triangulation T on S, denoted by $D_T$, is obtained as follows. We first draw an additional edge between $s_1$ and $s_n$ as an x-monotone curve that goes above all other points and segments. After that, $D_T$ is defined analogously to Definition 1.2. For the degenerate case $n=2$ we define $D_T$ to be a single edge with the corresponding vertical extensions at both endpoints.

Inserting an additional edge between the left-most and right-most point might seem rather arbitrary. However, apart from obtaining much nicer drawings, this is done for a natural reason that will become clear later.

Here, a closely related concept from graph drawing is that of upward triangulations. These are abstract maximal planar graphs with directed edges such that there exists a plane embedding where all edges are drawn as y-monotone Jordan curves pointing upwards [4]. After replacing upward with rightward (and y-monotone with x-monotone), and after looking at Fig. 2, it becomes clear that every trapezoidal diagram of a geometric triangulation corresponds to a unique upward triangulation (by orienting edges from left to right) and that, depending on the presence or absence of symmetries, every upward triangulation corresponds to either one or two such diagrams.

Fig. 2

An (abstract) upward (or rather, rightward) triangulation and two corresponding trapezoidal diagrams of (geometric) triangulations. The second diagram can be obtained by a vertical reflection

In Sect. 2 we present a generic method for encoding trapezoidal diagrams as strings over a finite alphabet. The presented ideas can be applied to any family of geometric graphs. However, we obtain a simple characterization of the set of code words only in the cases of perfect matchings and triangulations. Nevertheless, in all other cases it is easy to give at least exponential upper bounds of the form $\alpha ^n$ for some constant $\alpha$.

Let $\mathfrak {D}_n^{ \textsf {pm} }= \{D_M\}$ be the set of all diagrams of all perfect matchings on all point sets S of size n. See Table 1 for an enumeration of this set for $n = 0,2,4$.

Table 1 All non-isomorphic trapezoidal diagrams of perfect matchings, with $\varnothing$ the empty diagram

Theorem 1.4

For any $n = 2m$, the number of trapezoidal diagrams of perfect matchings on n points is equal to the mth 3-dimensional Catalan number, i.e.,

$$\begin{aligned} |\mathfrak {D}_n^{ \textsf {pm} }| = C^{(3)}_m = \frac{2(3m)!}{(m+2)!(m+1)!m!} \sim \beta n^{-4} \alpha ^n \; (\text {as }n \rightarrow \infty ), \end{aligned}$$

where

$$\begin{aligned} \alpha = \sqrt{27} \approx 5.19615, \; \text { and } \; \beta = \frac{16\sqrt{3}}{\pi } \approx 8.82126. \end{aligned}$$

Similarly, let $\mathfrak {D}_n^{ \textsf {tr} }= \{D_T\}$ be the set of all diagrams of all triangulations on all sets S of size n as specified in Definition 1.3. Enumerations of this set for the cases $n = 2,3,4,5$ can be seen in Table 2.

Table 2 All non-isomorphic trapezoidal diagrams of triangulations

Theorem 1.5

For any $n = m+2$, the number of trapezoidal diagrams of triangulations on n points is equal to the mth 3-dimensional prime Catalan number, i.e.,¹

$$\begin{aligned} |\mathfrak {D}_n^{ \textsf {tr} }| = P^{(3)}_m = \Theta ^*(\gamma _3^n), \; \text { where } \gamma _3 = \frac{27}{({729\sqrt{3}}/({40\pi }) - 9)^3} \approx 23.45948. \end{aligned}$$

The following corollary should be compared with a classic result of Tutte [15], which implies that the number of abstract triangulations (i.e., maximal planar graphs) on n vertices is $\Theta ^*(\alpha ^n)$, where $\alpha = 256/27 \approx 9.481$. Moreover, quite curiously, in a side remark of [2] Alvarez and Seidel report an upper bound of $27^n$ on the number of upward triangulations. As we shall see, the appearance of the exponential base 27 in this context is not at all coincidental.

Corollary 1.6

Let $N_n$ be the number of upward triangulations on n vertices. Then, we have $|\mathfrak {D}_n^{ \textsf {tr} }|/2 \le N_n \le |\mathfrak {D}_n^{ \textsf {tr} }|$ and hence also $N_n = \Theta ^*(\gamma _3^n)$.

On a different note, Frati, Gudmundsson and Welzl [4] proved that the number of upward orientations of any given abstract triangulation is somewhere between $O^*(4^n)$ and $\Omega ^*(1.189^n)$, and that it can be as low as $O^*(2^n)$ and as high as $\Omega ^*(2.599^n)$ in specific cases. Combined with Tutte’s result, the preceding corollary now implies that an abstract triangulation has $\Theta ^*(\beta ^n)$ upward orientations on average, where $\beta = \gamma _3/\alpha \approx 2.474$ and $\alpha$ is as in Tutte’s result.

Embeddings.

Our interest in trapezoidal diagrams originally came from a desire for improved upper bounds on the maximum number of crossing-free geometric graphs on any set S of n points. A classic result due to Ajtai et al. [1] implies that, for any family of graphs, this maximum number is equal to $\Theta ^*(\alpha ^n)$ for some absolute constant $\alpha$. Upper bounds for these numbers have been improved gradually over the past decades, culminating in $\alpha \le 10.05$ for perfect matchings [11] and $\alpha \le 30$ for triangulations [10]. However, there are no matching lower bounds, and the general consensus is that the known upper bounds are still far away from the truth.

In Sect. 3 we initiate the study of the maximum number of embeddings that a given trapezoidal diagram can have on a fixed point set, by giving two exponential lower bounds.

2 Encoding Trapezoidal Diagrams

Let G be a crossing-free geometric graph of one of the investigated types. Fix a drawing of $D_G$ and consider the set of all points in the plane which are neither a vertex, nor part of an edge, nor a vertical extension. Then, a trapezoid in $D_G$ is defined as the closure of a maximal connected region in that set. Typically, but not always, a trapezoid is bounded from above and below by (parts of) edges of G, and to the left and right by vertical extensions.

Fig. 3

On the left, the canonical order of a trapezoidal diagram of a perfect matching. On the right, the boundaries corresponding to the prefixes $1,\ldots ,5$ and $1,\ldots ,15$

Fig. 4

On the left, the canonical order of a trapezoidal diagram of a triangulation. On the right, the boundary corresponding to the prefix $1,\ldots ,10$

We further define a canonical order over the trapezoids in $D_G$ in the following recursive manner. Given a prefix of the canonical order, we select as the next element a trapezoid that is either unbounded from below or that is bounded from below by an edge e which is already well-supported, in the sense that all trapezoids having e as their upper boundary occur in the given prefix of the canonical order. If the above choice is not unique, then we settle with the left-most option.

By the following observation, which follows by induction over the length of the given prefix, the canonical order is seen to be both well-defined and independent of the fixed drawing of $D_G$.

Observation 2.1

Take any proper (i.e., both non-empty and incomplete) prefix of the canonical order of $D_G$, build the union of all trapezoids in that prefix, and consider the boundary of that union. This boundary has a stair-case shape as depicted in Figs. 3 and 4. Specifically:

• Starting at positive infinity at the end of a vertical extension that is unbounded from above, the boundary alternates between verticals that go downwards and (parts of) not necessarily straight edges that go to the right, and it finally ends at negative infinity at the end of a vertical extension that is unbounded from below.

• Every vertical on the boundary contains exactly one vertex of G, either (a) at the bottom, (b) in its relative interior, or (c) at the top. When going along the boundary, we first encounter a (possibly empty) sequence of verticals of type (a), then at most one vertical of type (b), and then a (possibly empty) sequence of verticals of type (c).

Further note that the subsequent trapezoid in canonical order must be bounded to the left by the last vertical that is not of type (c).

We are ready to prove the following lemma. Combining it with (1) and (2) yields Theorem 1.4.

Lemma 2.2

For any $n = 2m$ there is a bijection between $\mathfrak {D}_n^{ \textsf {pm} }$ and the set of balanced bracket expressions of dimension 3 and of size m.

Proof

For $m = 0$ the claim is trivial. So let $m \ge 1$, and let us define mappings in both directions. Observing that these mappings are inverses of each other concludes the proof.

From trapezoids to brackets. Let $D = D_M$ be the trapezoidal diagram of an arbitrary perfect matching M on a set S of n points. We show how to construct the corresponding balanced bracket expression c of size m.

We first enumerate the trapezoids in D in canonical order, where we omit the last trapezoid on the far right. We obtain a sequence of exactly 3m trapezoids, each one of which is bounded to the right. Indeed, observe that to each edge $e = \{i,j\}$ in D, where $i < j$ are the respective left and right endpoints, we can attribute the following three trapezoids.

• (i) The unique trapezoid whose right boundary is the vertical extension through i.

• (ii) The unique trapezoid whose right boundary is the vertical extension below j.

• (iii) The unique trapezoid whose right boundary is the vertical extension above j.

In order to obtain c, we now apply the substitution rules $\text {(i)} \mapsto `\langle$’, $\text {(ii)} \mapsto `|$’, $\text {(iii)} \mapsto `\rangle$’, based on the three types of trapezoids specified above. The resulting string is a balanced bracket expression of size m because, as is clear from Observation 2.1, for each edge e the three attributed trapezoids occur in the relative order (i), (ii), (iii).

From brackets to trapezoids. Let c be an arbitrary balanced bracket expression of dimension 3 and of size m. We show how to construct the corresponding trapezoidal diagram $D = D_M$ of a perfect matching M on n points.

We iterate over c and construct a drawing of D by drawing one trapezoid per letter in c. For each bracket we select a different type of trapezoid. More precisely, as follows, we discriminate between the possible locations of the vertex i that lies on the right boundary of the new trapezoid.

In the illustrations above we have omitted to draw the vertices on the respective left boundaries. Also, the trapezoids of types (i) and (ii), but not (iii), might in fact be unbounded from below. Similarly, the trapezoids of type (i) and (iii), but not (ii), might be unbounded from above.

The positioning of individual trapezoids is done as illustrated in Table 3, where the labels l and r indicate whether a boundary vertex is a left or right endpoint. Mutations which involve unbounded trapezoids can be handled analogously. Also note that, after each step, the boundary of the union of all drawn trapezoids has a stair-case shape as in Observation 2.1, and the order in which we add trapezoids corresponds to the canonical order.

Table 3 Constructing the trapezoidal diagram of a perfect matching

We now have to show that, if c is a balanced bracket expression, then each trapezoid can be placed in a coherent way. Assume thus that we have processed a certain prefix of c already. Then, each left endpoint on the current boundary, except for those on a vertical of type (a) directly followed by a vertical of type (c) (as specified in Observation 2.1), is called an active left endpoint. In more descriptive terms, an active left endpoint is one whose corresponding right endpoint is not yet part of the construction. Similarly, each right endpoint on the current boundary, except for those on a vertical of type (b), is called an active right endpoint. That is, an active right endpoint is one which up to now has no trapezoid placed on top of it. Let now $m_1$, $m_2$ and $m_3$ be the respective numbers of occurrences of the brackets $`\langle$’, $`|$’ and $`\rangle$’ in the processed prefix of c. We claim that we maintain the following invariants.

• (I1) The number of active left endpoints on the boundary is equal to $m_1 - m_2$.

• (I2) The number of active right endpoints on the boundary is equal to $m_2 - m_3$.

These invariants are a consequence of the following simple observations: Adding a trapezoid of type (i) creates a new active left endpoint. Adding a trapezoid of type (ii) turns a formerly active left endpoint inactive, and it also creates a new active right endpoint. Adding a trapezoid of type (iii) turns a formerly active right endpoint inactive. Again, refer to Table 3 for helpful illustrations.

These invariants guarantee that we never get stuck when constructing D. Indeed, if the current bracket to be processed is $`\langle$’, then it is always possible to add a trapezoid of type (i). If the current bracket is $`|$’, then we can add a trapezoid of type (ii) only if there is an active left endpoint on the boundary, which is guaranteed by (I1) because the already processed prefix of c satisfies $m_1 > m_2$ (because c is a balanced bracket expression). If the current bracket is $`\rangle$’, then we can add a trapezoid of type (iii) only if there is an active right endpoint on the boundary, which is guaranteed by (I2) because the already processed prefix of c satisfies $m_2 > m_3$.

Also, by invariants (I1) and (I2), when the whole string c has been processed we end up with a boundary that consists of a single vertical with one inactive right endpoint. The last trapezoid (i.e., the one that is unbounded to the right) can then be added in order to finish the construction of D. $\square$

The proof of the next lemma is very similar to the preceding one. Combining the lemma with Theorem 1.1 and (3) yields Theorem 1.5.

Lemma 2.3

For any $n = m + 2$ there is a bijection between $\mathfrak {D}_n^{ \textsf {tr} }$ and the set of prime balanced bracket expressions of dimension 3 and of size m.

Proof

Assume again that $m \ge 1$. We proceed by defining mappings in both directions which are clearly inverses of each other.

From trapezoids to brackets. Let $D = D_T$ be the trapezoidal diagram of a triangulation T on a set of n points, as specified in Definition 1.3. We show how to construct the corresponding balanced bracket expression c of size m.

We start by enumerating the trapezoids in D in canonical order, where we only consider trapezoids that are enclosed by the double edge $\{1,n\}$. In other words, we ignore all four unbounded trapezoids. The reader should not be confused by the fact that all enumerated trapezoids have only one vertical boundary and hence look more like triangles. Further note that we get a sequence of 4m trapezoids in this way. Indeed, to each of the m inner vertices $i \in [n] \setminus \{1,n\}$ we can attribute the following four trapezoids.

• (i) The unique trapezoid whose right boundary is the vertical extension below i.

• (ii) The unique trapezoid whose right boundary is the vertical extension above i.

• (iii) The unique trapezoid whose left boundary is the vertical extension below i.

• (iv) The unique trapezoid whose left boundary is the vertical extension above i.

As a consequence of Observation 2.1, the trapezoids of type (ii) and (iii) attributed to a common vertex i always appear consecutively in the order (ii), (iii). Therefore, similar to what we did in the proof of Lemma 2.2, we construct c by applying the substitution rules $\text {(i)} \mapsto `\langle$’, $\text {(ii),(iii)} \mapsto `|$’, $\text {(iv)} \mapsto `\rangle$’. Note that in the case of the second rule we effectively replace two trapezoids with one single bracket. Also, by Observation 2.1, the four trapezoids attributed to a common vertex i occur in the relative order (i), (ii), (iii), (iv), implying that c is indeed a balanced bracket expression of size m. In what follows we will further see that c is prime.

From brackets to trapezoids. Let c be an arbitrary balanced bracket expression of size m. For the time being, we do not make the assumption that c is prime. We will try (and gracefully fail) to construct the corresponding trapezoidal diagram $D = D_T$ of a triangulation T on n points.

We start by drawing the two obvious initial unbounded trapezoids. We then iterate over c and draw one or two trapezoids per letter in c. Depending on the brackets we make the following selections.

As for the positioning of individual trapezoids, we do it again in the obvious way by trying to maintain the invariant that, after each step, the boundary has a stair-case shape as in Observation 2.1. In fact, if we regard the addition of the two trapezoids of type (ii,iii) as one single step, then the boundary will never contain any verticals of type (b) (as specified in Observation 2.1). Helpful illustrations can be seen in Table 4.

Table 4 Constructing the trapezoidal diagram of a triangulation

Assume now that we have processed a certain prefix of c already. Then, every vertex on a vertical of type (a), except for the right-most one, is called an active left endpoint. Similarly, every vertex on a vertical of type (c), except for the left-most one, is called an active right endpoint. For $m_1$, $m_2$ and $m_3$ as in the proof of Lemma 2.2, we claim that we maintain the following invariants.

• (I1) The number of active right endpoints on the boundary is equal to $m_1 - m_2$.

• (I2) The number of active left endpoints on the boundary is equal to $m_2 - m_3$.

These invariants once more follow from three simple observations: Adding a trapezoid of type (i) turns a formerly inactive right endpoint active. Adding a pair of trapezoids of type (ii,iii) turns a formerly active right endpoint inactive, and it also turns a formerly inactive left endpoint active. Adding a trapezoid of type (iv) turns a formerly active left endpoint inactive.

The above invariants guarantee that we never get stuck when constructing D, even if c is not prime. Indeed, if the current bracket to be processed is $`\langle$’, then we can always add a trapezoid of type (i). If the current bracket is $`|$’, then we can add a trapezoid of type (ii,iii) only if there is an active right endpoint, which is guaranteed by (I1) because the already processed prefix of c satisfies $m_1 > m_2$. If the current bracket is $`\rangle$’, then we can add a trapezoid of type (iv) only if there is an active left endpoint, which is guaranteed by (I2) because the already processed prefix of c satisfies $m_2 > m_3$.

Furthermore, when c has been processed completely, invariants (I1) and (I2) imply that the boundary consists of a single edge and two unbounded verticals (in other words, the staircase consists of a single step). Hence, we can just add the two final unbounded trapezoids in order to finish the construction of D.

Fig. 5

Substrings which are balanced bracket expressions lead to unwanted double edges

Figure 5 shows that not every balanced bracket expression c is mapped to a valid trapezoidal diagram. It can happen that double edges are created. Recall that one double edge between vertices 1 and n is required, but any other double edge or even a triple edge between vertices 1 and n is not in accordance with Definition 1.3. All the same, we now see that the above reconstruction procedure creates a double edge whenever it finishes processing a substring of c that is itself a balanced bracket expression. Since the described mapping clearly computes the inverse of the earlier mapping that goes in the other direction, this also implies that all balanced bracket expressions produced by that first mapping are in fact prime.

Lastly, we face the problem of stretchability, namely that the produced drawing D might not correspond to the trapezoidal diagram $D_T$ of an actual triangulation T (with straight-line segments). However, it is known that any simple plane graph with edges drawn as non-crossing x-monotone curves can be stretched without changing edge orientations with respect to the x-axis [6, Thm. 4]. If c is prime, it thus follows that also our drawing D is stretchable after removing the upper copy of the double edge $\{1,n\}$. $\square$

3 Embeddings of Trapezoidal Diagrams

Fix a diagram D with n vertices and a set S of n points. An embedding of D on S is a crossing-free geometric graph G on S with $D_G = D$. Recall that for any family of crossing-free geometric graphs, the maximum number of such graphs on any set of n points equals $\Theta ^*(\alpha ^n)$ for some constant $\alpha$. If embeddings of D on every fixed S had turned out to be unique, then Theorems 1.4 and 1.5 would have implied the improved bounds $\alpha \le 5.196$ for perfect matchings and $\alpha \le 23.459$ for triangulations. However, since embeddings are not unique in general, a natural follow-up question asks for the maximum number of embeddings. While so far we did not succeed to obtain adequate upper bounds for these quantities, we can present two simple exponential lower bounds.

As already seen in Fig. 1, there exists a diagram of a perfect matching with $m=6$ edges that can be embedded in two different ways on a set of $n=12$ points. By repeating that construction side by side as illustrated in Fig. 6, we get the following amplification.

Fig. 6

A point set where many distinct perfect matchings have the same trapezoidal diagram. Only one of $2^5 = 32$ such perfect matchings is shown

Theorem 3.1

For any k there exists a planar point set $S_k$ of size $n = 10k + 2$ and a diagram $D \in \mathfrak {D}_n^{ \textsf {pm} }$ with $2^k = \Omega (1.071^n)$ distinct embeddings on $S_k$.

Proof

To construct $S_k$, put k blocks, each one consisting of a copy of the point set from Fig. 1, side by side, but draw the respective left-most and right-most points only once, as exemplified in Fig. 6 for $k=5$. In this way we get ten points per block and two extra points, giving a total of $10k + 2$ points. The diagram D is chosen as a natural extension of the one seen in Fig. 1. Observe now that for each block we can choose one of two distinct ways to embed the corresponding part of D. Furthermore, these binary choices can be made independently, implying the desired number of $2^k$ embeddings.$\square$

For triangulations we present an analogous construction. It is based on the point set depicted in Fig. 7, which is an adaptation of a point set taken from [2] due to Günter Rote. Originally, it was used to show that embeddings of upward triangulations on a given point set are not always unique.

Theorem 3.2

For any k there exists a planar point set $S_k$ of size $n = 12k^2 + 4k + 3$ and a diagram $D \in \mathfrak {D}_n^{ \textsf {tr} }$ with $2^{k^2} = \Omega (1.059^n)$ distinct embeddings on $S_k$.

Proof

Define a block as a copy of the point set depicted in Fig. 7. Arrange $k^2$ such blocks in a honey comb grid, where extreme points of individual blocks may coincide with extreme points of neighboring blocks. Place three additional points such that $S_k$ has a triangular convex hull. It can be checked that this gives a total of $12k^{2} + 4k + 3$ points. The diagram D is chosen accordingly as a honey comb grid consisting of $k^2$ copies of the diagram depicted in Fig. 7 and some extra edges for connecting the hull vertices. The desired number of embeddings again follows after observing that we have independent binary choices for embedding individual blocks. $\square$

Fig. 7

A point set and two triangulations which have the same trapezoidal diagram

4 Prime Catalan Numbers

In this final section we present all ingredients that are required to prove Theorem 1.1 from the introduction. Furthermore, we show how to compute prime Catalan numbers efficiently.

In order to make notation less cumbersome when dealing with (prime) Catalan numbers of arbitrary dimension, we omit writing the superscripts (d), but we always keep in mind the dependency on d. That is, we write $C_m = C^{(d)}_m$ and $P_m = P^{(d)}_m$. We further define the ordinary generating functions

$$\begin{aligned} C(x) = \sum _{m=0}^\infty C_m x^m, \qquad P(x) = \sum _{m=0}^\infty P_m x^m. \end{aligned}$$

(4)

We will be using a fundamental result of complex function theory called the Lagrange inversion formula. In its classic form, it gives the Taylor expansion of the inverse of an analytic function at a point where the first derivative does not vanish. In combinatorics, the following formulation is often most useful [3, Thm. A.2].

Theorem 4.1

(Lagrange Inversion) Let $A(x) = \sum _{m=0}^\infty A_mx^m$ be a formal power series satisfying $A_0 \ne 0$. Define $Z(x) = {x}/{A(x)}$. Then, there exists a unique compositional inverse of Z(x), i.e., a unique formal power series $X(z) = \sum _{m=0}^\infty X_m z^m$ which satisfies $Z(X(z)) = z$. Moreover, the coefficients of X(z) and $X(z)^k$ are given by

$$\begin{aligned}{}[z^m]\,X(z) = \frac{1}{m}\, [x^{m-1}]\, A(x)^m, \qquad [z^m]\,X(z)^k = \frac{k}{m}\, [x^{m-k}]\, A(x)^m. \end{aligned}$$

We will also be using a multiplicative variant of Fekete’s lemma. For a proof we refer the reader to [16, Lem. 11.6].

Theorem 4.2

(Fekete’s Lemma) Let $A_0,A_1,A_2,\ldots$ be a sequence of non-negative real numbers such that $A_{m+n} \ge A_m \cdot A_n$ holds for all m, n. Then

$$\begin{aligned} \lim _{m \rightarrow \infty } \root m \of {A_m} = \limsup _{m \rightarrow \infty } \root m \of {A_m}. \end{aligned}$$

In particular, the limit exists unless it diverges to infinity.

We start by proving the following lemma, which establishes a formal relation between C(x) and P(x), and hence between the numbers $C_m$ and $P_m$.

Lemma 4.3

For any dimension d, the functional equation $C(x) = P(xC(x)^d)$ holds.

Proof

Let c be a balanced bracket expression of dimension d. Consider now all inclusion-maximal and contiguous substrings of c which are themselves balanced bracket expressions (of dimension d) and which start someplace after the first letter of c. Call these substrings $c_1,c_2,\ldots ,c_k$ and note that some of them might be empty (see Fig. 8 for an example for $d=3$). In fact, by definition, we have $|c_1| = |c_2| = \ldots = |c_k| = 0$ if and only if c is prime.

Fig. 8

A balanced bracket expression c, and the corresponding factorization consisting of p and $c_1,\ldots ,c_6$

Clearly, for $i \ne j$, $c_i$ and $c_j$ cannot be adjacent in c since they are inclusion-maximal by assumption. Nor does $c_i$ contain $c_j$ or vice versa. Nor do they overlap because if that were the case, both their intersection and their union would be balanced bracket expressions, again contradicting inclusion-maximality.

Therefore, after removing $c_1,\ldots ,c_k$ from c, we obtain a balanced bracket expression p that is prime, whose size satisfies $d \cdot |p| = k$, and which yields back c if $c_1,\ldots ,c_k$ are plugged back into the k gaps in p in the appropriate order (we ignore the “gap” before the first letter in p). Loosely speaking, the ordered collection consisting of p and $c_1,\ldots ,c_k$ can be seen as a unique factorization of c. Further note that we have $|c| = |p| + |c_1| + \cdots + |c_k|$.

In the sums below, by letting the variables c and $c_1,\ldots ,c_k$ run over all balanced bracket expressions of dimension d, and by letting p run over all expressions that are prime, we now see that, indeed,

$$\begin{aligned} C(x)&= \sum _c x^{|c|} = \sum _p \sum _{\begin{array}{c} c_1,\ldots ,c_k \\ k = d \cdot |p| \end{array}} x^{|p| + |c_1| + \cdots + |c_k|} \\&= \sum _p x^{|p|} \sum _{{\begin{array}{c} c_1,\ldots ,c_k \\ k = d \cdot |p| \end{array}}} x^{|c_1| + \cdots + |c_k|} = \sum _p x^{|p|} C(x)^{d \cdot |p|} = P(xC(x)^d). \end{aligned}$$

$\square$

By combining Lemma 4.3 with the Lagrange inversion formula, we obtain an efficient method for computing prime Catalan numbers of any dimension.

Lemma 4.4

For any dimension d, we have $\displaystyle P_m = \frac{1}{1-dm} \cdot [x^m]\, \frac{1}{C(x)^{dm-1}}$.

Proof

Define the formal power series

$$\begin{aligned} A(x) := \frac{1}{C(x)^d}, \qquad Z(x) := \frac{x}{A(x)} = xC(x)^d. \end{aligned}$$

(5)

By Theorem 4.1, there exists X(z) with $Z(X(z)) = z$. Hence, substituting X(z) for x in Lemma 4.3 yields $C(X(z)) = P(z)$. Observe now that for $m=0$ the lemma holds because we have $P_0 = C_0 = 1$. For $m > 0$, by using the formula from Theorem 4.1 in the fourth step [i.e., fourth equality in (6)],

$$\begin{aligned} \begin{aligned} P_m&= [z^m]\, P(z) = [z^m]\, C(X(z)) \\&= \sum _{k=0}^\infty C_k \cdot [z^m]\, X(z)^k \\&= \sum _{k=0}^\infty C_k \cdot \frac{k}{m} \,[x^{m-k}]\, A(x)^m = \frac{1}{m} \cdot [x^m]\, A(x)^m \cdot \underbrace{\sum _{k=0}^\infty k C_k x^k}_{\smash {= \, xC'(x)}} \\&= \frac{1}{m} \cdot [x^{m-1}]\, \frac{C'(x)}{C(x)^{dm}} = \frac{1}{m} \cdot [x^{m-1}] \left( \frac{1}{1-dm}\, \frac{1}{C(x)^{dm-1}}\right) ' \\&= \frac{1}{1-dm} \cdot [x^m] \,\frac{1}{C(x)^{dm-1}}. \end{aligned} \end{aligned}$$

(6)

$\square$

In the introduction we observed that for $d=2$, the prime Catalan numbers do not give us a particularly exciting sequence. For higher dimensions the situation is very different, as shown by the next lemma.

Lemma 4.5

For any dimension $d \ge 3$, the prime Catalan numbers are super-multi-plicative, i.e., $P_{m+n} \ge P_m \cdot P_n$ for all m and n.

Proof

Fix m and n. Consider the two sets of sizes $P_m$ and $P_n$ containing all prime balanced bracket expressions of size m and n, respectively. By combining each pair of such expressions in a certain way, we will show how to obtain $P_m \cdot P_n$ distinct prime balanced bracket expressions of size $m+n$.

Let now $p_m$ and $p_n$ be two arbitrary prime balanced bracket expressions of respective sizes m and n. We may assume that m and n are both non-zero. In that case, however, the two expressions must be of the forms $p_m = p_m' \rangle$ and $p_n = \langle p_n'$, where $p_m'$ and $p_n'$ are the prefix and postfix, respectively, of $p_n$ and $p_m$, containing all but one letter. Here, we have used the brackets $b_1 = `\langle$’ and $b_d = `\rangle$’, while leaving the remaining $d-2$ brackets unspecified. The expression corresponding to the pair $(p_m,p_n)$ can now be defined as $p = p_m' \langle \rangle p_n'$. Clearly, in this way we obtain $P_m \cdot P_n$ distinct balanced bracket expressions of size $m+n$. It only remains to show that p is prime.

Consider thus a substring c of p that is a balanced bracket expression (of dimension d). Since by assumption $p_m$ and $p_n$ do not contain any such substrings, c must contain the central “$\langle \rangle$” between $p_m'$ and $p_n'$ in p. Fittingly, we write $c = c_m' \langle \rangle c_n'$, where $c_m'$ and $c_n'$ are a postfix and prefix, respectively, of $p_m'$ and $p_n'$. Furthermore, let $c_m = c_m'\rangle$ and $c_n = \langle c_n'$. The fact that $c_m'$ and $c_m$ are, respectively, a prefix and a postfix of a balanced bracket expression easily implies that $c_m$ is a balanced bracket expression. By a symmetric argument, $c_n$ is also a balanced bracket expression. Since $p_m$ and $p_n$ are prime, it follows that $c_m = p_m$ and $c_n = p_n$, and thus $c = p$. $\square$

Theorem 1.1 from the introduction is a consequence of Lemma 4.5, Theorem 4.2, and the fact that the radius of convergence of the formal power series P(x) is equal to $1/\gamma _d$. The latter is not hard to prove by using Lemma 4.3 and by using that the radius of convergence of C(x) is equal to $1/d^d$.

Theorem 4.1

For any dimension $d \ge 3$, the prime Catalan numbers satisfy

$$\begin{aligned} \lim _{m \rightarrow \infty } \root m \of {P_m} = \gamma _d, \; \text { where } \gamma _d := \left( \frac{d}{C(1/d^d)}\right) ^d. \end{aligned}$$

Proof

For any fixed dimension $d \ge 3$, let $R_C$ and $R_P$ be the radii of convergence of the power series C(x) and P(y), respectively. From the hook-length formula and Stirlings’s approximation (see (1) and (2) for the 3-dimensional case), it follows that

$$\begin{aligned} C_m \sim \frac{1! \cdot 2! \cdots (d-1)! \cdot \sqrt{d}}{\sqrt{2\pi }^{d-1}} \,m^{-(d^2-1)/2}d^{dm}\; (\text {as }m \rightarrow \infty ), \end{aligned}$$

(7)

and hence, by elementary analysis,

$$\begin{aligned} R_C = 1/d^d. \end{aligned}$$

(8)

From (7) and (8) we will deduce that $R_P = 1 / \gamma _d$. This will conclude the proof of the theorem because of Lemma 4.5 and Theorem 4.2.

First, we show that $R_P \ge 1/\gamma _d$. Note that for positive $x < R_C$, the function C(x) is continuous and strictly increasing, since all coefficients are positive. It follows that for every positive $y < 1/\gamma _d = R_C C(R_C)^d$ there exists a (unique) positive $x < R_C$ with $y = xC(x)^d$ and hence, with the help of Lemma 4.3,

$$\begin{aligned} P(y) = P(xC(x)^d) = C(x) < \infty . \end{aligned}$$

(9)

Second, we show that $R_P \le 1/\gamma _d$. Since the radius of convergence does not change under differentiation, it is sufficient to prove that the formal derivative of P(y) of a certain order diverges at $y = 1/\gamma _d$. For that, we will use the following elementary observations.

• The kth derivative² $C^{(k)}(R_C)$ remains convergent for $k < ({d^2-1})/{2}-1$, but diverges for all $k \ge ({d^2-1})/{2}-1$ (this follows from (7) by a comparison with hyperharmonic series).

• We have $C^{(k)}(x) > 0$ for any $k \ge 0$ and all positive $x \le R_C$ (simply because all coefficients of C(x) are positive).

Let now $F(x) = xC(x)^d$, and consider the first derivative

$$\begin{aligned} F'(x) = dxC(x)^{d-1} \cdot C'(x) + C(x)^d, \end{aligned}$$

(10)

as well as the kth derivative

$$\begin{aligned} F^{(k)}(x) = dxC(x)^{d-1} \cdot C^{(k)}(x) + \cdots , \end{aligned}$$

(11)

where we have omitted all the additive terms that contain only lower-order derivatives of C(x).

Starting from the equality given by Lemma 4.3, we similarly get

$$\begin{aligned} P'(F(x)) = \frac{C'(x)}{F'(x)}, \end{aligned}$$

(12)

as well as

$$\begin{aligned} P^{(k)}(F(x)) = \frac{C^{(k)}(x)}{F'(x)^k} - \frac{F^{(k)}(x)C'(x)}{F'(x)^{k+1}} + \cdots , \end{aligned}$$

(13)

where again we have omitted additive terms that contain only lower-order derivatives of C(x) and F(x). By combining (13) with (11) and (10) we obtain the following.

$$\begin{aligned} P^{(k)}(F(x))&= \frac{C^{(k)}(x)}{F'(x)^k} \Bigg (1 - \frac{dxC(x)^{d-1}C'(x)}{F'(x)}\Bigg ) + \cdots \end{aligned}$$

(14)

$$\begin{aligned}&= C^{(k)}(x) \cdot \frac{C(x)^d}{F'(x)^{k+1}} + \cdots \end{aligned}$$

(15)

Using our observations, for $k = \lceil ({d^2-1})/{2}-1\rceil \ge 2$, as x approaches $R_C$ from below, the right hand side of (15) diverges because $C^{(k)}(x)$ tends to infinity and because all omitted additive terms are bounded. $\square$

As expected, the argument in the proof of Theorem 1.1 breaks down for the case $d=2$. Indeed, for $d=2$ we get $k = \lceil ({d^2-1})/{2}-1\rceil = 1$, which means $F'(x)$ is no longer bounded and we cannot conclude that the right hand side of (15) tends to infinity. In fact, it does not diverge, since $P(y) = 1 + y$ and $P'(y) = 1$ for $d=2$.

Experiments

In Tables 5, 6, 7 we present some experimental evidence for the asymptotic growth rate of the prime Catalan numbers of dimensions $d = 3,4,5$.

For $d = 3$ the corresponding approximations are defined as

$$\begin{aligned} \tilde{C}^{\smash {(3)}}_m := m^{-4} 3^{3m} \qquad \tilde{P}^{\smash {(3)}}_m := m^{-4} \gamma _3^m ,\;\;\;\text { where } \gamma _3 = \frac{27}{({729\sqrt{3}}/({40\pi }) - 9)^3}. \end{aligned}$$

Note that, as can be expected from (2), the ratio $C^{\smash {(3)}}_m / \tilde{C}^{\smash {(3)}}_m$ approaches ${\sqrt{3}}/{\pi } \approx 0.55132$ as m grows larger. Also the ratio $P^{\smash {(3)}}_m / \tilde{P}^{\smash {(3)}}_m$ seems to converge, but we do not know the limit.

Similarly, for $d = 4$ we define

$$\begin{aligned} \tilde{C}^{(4)}_m := m^{-7.5} 4^{4m}&\tilde{P}^{(4)}_m := m^{-7.5} \gamma _4^m,\;\;\;\text { where }\gamma _4 \approx 251.78874. \end{aligned}$$

Finally, for $d = 5$ we define

$$\begin{aligned} \tilde{C}^{(5)}_m := m^{-12} 5^{5m}&\tilde{P}^{(5)}_m := m^{-12} \gamma _5^m,\;\;\;\text { where }\gamma _5 \approx 3119.93434. \end{aligned}$$

Table 5 Experimental data for 3-dimensional (prime) Catalan numbers

Table 6 Experimental data for 4-dimensional (prime) Catalan numbers

Table 7 Experimental data for 5-dimensional (prime) Catalan numbers