The Central Component of a Triangulation

Alon Regev Department of Mathematical Sciences Northern Illinois University DeKalb, IL 60115 USA

                      regev@math.niu.edu

Abstract

We define the central component of a triangulation of a regular convex polygon as the diameter or triangle containing its geometric center. This definition yields a new recursion relation for Catalan numbers, which can be used to derive congruence relations. We generalize this idea to k-angulations, giving congruences of k-Catalan numbers. We also enumerate the triangulations that include a fixed vertex in their central components.

1 Introduction

Considering a triangulation of a regular convex polygon as a subset of ℝ^{2} centered at the origin, define its central component to be the diameter or triangle that contains the origin (see Figure 1). More generally, every dissection of a polygon can be associated with its set of components, including one central component. Bowman and the author used components and central components to enumerate symmetry classes of dissections in a paper [2], where these notions are more formally defined. In this note we use central components to obtain new recursion relations for Catalan and k-Catalan numbers, and use these recursions to prove congruence relations of these numbers. We also enumerate the triangulations that include a fixed vertex in their central components.

Let C_{n} be the n-th Catalan number, so C_{n−2} is the number of triangulations of an n-gon, and let C_{x} = 0 unless x is a nonnegative integer. The Catalan numbers satisfy the recursion

∑_{k=0}^{n} C_{k}C_{n−k} = C_{n+1}.  (1)

Figure 1: A central triangle with n = 12, i = 3, j = 4 and k = 5.

Consider a triangulation of an n-gon as a labeled graph with vertices 0, 1, …, n − 1 and edges denoted xy for distinct vertices x and y. The edges include n sides 01, 12, …, (n − 1)0 and n − 3 diagonals. The cyclic length of an edge xy, with x < y, is defined as

min{y − x, n + x − y}.

By enumerating the triangulations of an n-gon according to their central components, we obtain the following new recursion relation, which is one of the main results of this paper.

Lemma 1. For any n ≥ 3,

C_{n−2} = \frac{n}{2}C_{n/2−1}^{2} + ∑_{\begin{matrix}i+j+k=n \\ i≤j≤k<n/2 \end{matrix}} m_{ijk}C_{i−1}C_{j−1}C_{k−1},  (2)

where

m_{ijk} = \begin{cases}\frac{n}{3}, & if i = j = k; \\ n, & if i < j = k or i = j < k; \\ 2n, & if i < j < k. \end{cases}

Proof. The first term of (2) enumerates the triangulations whose central component is a diameter: there are n/2 possible positions for a diameter, and for each of these there are C_{n/2−1} triangulations of each of the two resulting (n/2 + 1)-gons. In the summation, m_{ijk} is the number of ways to position a triangle whose sides have cyclic lengths i, j, k inside an n-gon (see Figure 1). The conditions under the summation ensure that indeed this is a central triangle. The three cases determining m_{ijk} correspond to the central triangle being equilateral, isosceles or scalene. Each position of the triangle results in an (i + 1)-gon, a (j + 1)-gon and a (k + 1)-gon, and these can be triangulated in C_{i−1}, C_{j−1}, and C_{k−1} ways, respectively.

2 Congruence relations

Congruence relations of Catalan numbers C_{n} and related sequences have been the object of extensive study (see [1, 3] and the references therein). We next show that Lemma 1 can be used to derive some results of this nature. Note that the following result can also be proved using (1). In what follows we use the notation

t_{ijk} = m_{ijk}C_{i−1}C_{j−1}C_{k−1},

with m_{ijk} as in Lemma 1.

Theorem 2. C_{n} is odd if and only if n = 2^{a} − 1 for some integer a ≥ 0.

Proof. We use induction on n, with the base cases easily verified. The proof will follow from the next observation: the term t_{ijk} (with i ≤ j ≤ k) is odd if and only if i = 1 and j = k = 2^{c} for some c ≥ 1. To see this, first note that by induction, any term of the form t_{1,2^{c},2^{c}} is odd. Conversely, if t_{ijk} is odd then by induction, i = 2^{b}, j = 2^{c} and k = 2^{d} for some 0 ≤ b ≤ c ≤ d. Since n = 2^{b} + 2^{c} + 2^{d} is odd it follows that b = 0, and since m_{ijk} is odd then c = d as claimed.

Now let n = 2^{a} + 1, with a ≥ 1. On the right hand side of (2) we have C_{n/2−1} = 0, and the observation above implies that t_{ijk} is odd for exactly one term of the summation, so C_{n−2} is odd.

Conversely, suppose that C_{n−2} is odd. If n is even then so are the terms t_{ijk}, so that \frac{n}{2}C_{n/2−1}^{2} must be odd. Therefore n/2 is odd, and at the same time by induction n/2 = 2^{b} for some b ≥ 0. Thus b = 0 and n = 0 = 2^{0} − 1. If n is odd then C_{n/2−1} = 0, so at least one of the t_{ijk} must be odd, and by the observation above this implies n = 1 + 2^{c} + 2^{c} = 1 + 2^{c+1}, completing the proof.

We next use Lemma 1 to prove a recent result of Eu, Liu and Yeh [4]. Another proof is given by Xin and Xu [8, Theorem 5].

Theorem 3. [4, Theorem 2.3] For all n ≥ 0,

C_{n} ≡_{4} \begin{cases}1, & if n = 2^{a} − 1 for some a ≥ 0; \\ 2, & if n = 2^{a} + 2^{b} − 1 for some b > a ≥ 0; \\ 0, & otherwise. \end{cases}  (3)

Proof. In what follows, we repeatedly make use without mention of Theorem 2 and of the uniqueness of binary representation. By verifying the base cases we may assume n ≥ 10 and proceed by induction on n. Consider the three cases on the right hand side of (3).

1. The case n = 2^{a} − 1:

Let n = 2^{a} + 1 with a ≥ 4, and we show that C_{n−2} ≡_{4} 1. Reducing (2) modulo 4 gives

C_{n−2} ≡_{4} ∑_{\begin{matrix}i+j+k=n \\ i≤j≤k<n/2 \end{matrix}} m_{ijk}C_{i−1}C_{j−1}C_{k−1}.  (4)

Since C_{2^{a−1}−1} is odd,

t_{1,2^{a−1},2^{a−1}} = nC_{0}C_{2^{a−1}}C_{2^{a−1}} ≡_{4} 1,  (5)

and in fact this is the only term not divisible by 4. To see this, consider the terms for which t_{ijk} ≢_{4} 0.

(a) Suppose i = j = k. Then C_{i−1} must be odd, so i = 2^{c} for some c ≥ 0. Therefore

3(2^{c} − 1) = i + j + k = n = 2^{a} + 1,

or equivalently, 2^{c+1} + 2^{c} = 2^{a} + 2^{2}. Therefore a = 3, c = 2 and n = 9, contrary to the assumption that n ≥ 10.

(b) Suppose i = j < k. Then C_{i−1} must be odd, so i = j = 2^{c} for some c ≥ 0. Since C_{k−1} ≢_{4} 0, by induction either k = 2^{d} with d > c, or k = 2^{d} + 2^{e} with e > d ≥ c. In the former case, this implies

2^{a} + 1 = 2i + k = 2^{c+1} + 2^{d},

and in the latter case

2^{a} + 1 = 2^{c+1} + 2^{d} + 2^{e},

both cases resulting in a contradiction.

(c) Suppose i < j = k. As above, it follows that j = k = 2^{e} and either i = 2^{c}, with e > c, or i = 2^{c} + 2^{d}, with e ≥ d > c. In the former case,

2^{a} + 1 = i + 2j = 2^{c} + 2^{e+1},

which implies c = 0 and e = a − 1, yielding the term given by (5). The latter case again results in a contradiction.

(d) Suppose i < j < k. Since m_{ijk} is even, C_{i−1}C_{j−1}C_{k−1} must be odd. Therefore i = 2^{c}, j = 2^{d} and k = 2^{e} for some e > d > c ≥ 0, but then 2^{e} + 2^{d} + 2^{c} = 2^{a} + 1, which is impossible.

2. The case n = 2^{a} + 2^{b} − 1:

Let n = 2^{a} + 2^{b} + 1, and we show that C_{n−2} ≡_{4} 2. If a = 0, then n/2 − 1 = 2^{b−1}, so by induction on b we have C_{n/2−1} ≡_{4} 2. If a ≥ 1, then by definition C_{n/2−1} = 0. In either case, (4) still holds. Note that C_{2^{0}} = 1 and if a ≥ 1 then by induction C_{2^{a}} ≡_{4} 2. Therefore

t_{2^{a}+1,2^{b−1},2^{b−1}} = nC_{2^{a}}C_{2^{b−1}−1}C_{2^{b−1}−1} ≡_{4} 2.  (6)

Again, we show that all other t_{ijk} are divisible by 4, by considering the terms for which t_{ijk} ≢_{4} 0.

(a) Suppose i = j = k. Then we must have i = 2^{c} for some c ≥ 0, but this implies

2^{c+1} + 2^{c} = n = 2^{a} + 2^{b} + 1,

which is impossible for sufficiently large n.

(b) Suppose i < j < k. Then C_{i−1}C_{j−1}C_{k−1} is odd, so i = 2^{c}, j = 2^{d} and k = 2^{e} for some e > d > c ≥ 0. Therefore

2^{c} + 2^{d} + 2^{e} = n = 2^{a} + 2^{b} + 1.

Since we may assume a ≥ 1 (otherwise 2n ≡_{4} 0), it follows that c = 0, d = a and e = b. But this implies k ≥ n/2, contrary to the conditions under the summation.

(c) Suppose that i < j = k. Since C_{k−1} must be odd, k = 2^{e} for some e ≥ 0. Now if i = 2^{d} for some d < e then

2^{a} + 2^{b} + 1 = 2^{d} + 2^{e+1},

which is impossible. Therefore by induction we have i = 2^{c} + 2^{d}, with e > d > c ≥ 0. This gives

2^{a} + 2^{b} + 1 = i + 2k = 2^{c} + 2^{d} + 2^{e+1},

so c = 0 and 2^{a} + 2^{b} = 2^{d} + 2^{e+1}. It follows that e = b − 1 and d = a, which is the term given by (6). A similar analysis of the case i = j < k results in a contradiction.

3. Otherwise:

We show that C_{n−2} ≡_{4} 0 unless n − 2 has one of the forms above. If C_{n/2−1}^{2} ≢_{4} 0 then n/2 = 2^{a} for some a ≥ 0. For n sufficiently large this implies 8|n so that \frac{n}{2}C_{n/2−1}^{2} ≡_{4} 0. Next, consider the terms for which t_{ijk} ≢_{4} 0.

(a) Suppose i = j = k. Since C_{n/3−1}^{3} ≢_{4} 0, we must have n/3 = 2^{a} for some a ≥ 0. Thus n = 3 · 2^{a}. However, for sufficiently large n this would imply that m_{ijk} = n/3 ≡_{4} 0.

(b) Suppose i = j < k or i < j = k. If C_{i−1}C_{j−1}C_{k−1} is odd then

n = 2^{b+1} + 2^{c}  (7)

for some b, c ≥ 0 . Now

2^{c} < n/2 = 2^{b} + 2^{c−1},

so c−1 < b and in fact c < b (since c−1 = b would imply n = 2^{c} ≡_{4} 0). Therefore (7) implies that c = 0 or c = 1, so n − 2 = 2^{b+1} − 1 or n − 2 = 2^{b+1} + 2^{0} − 1. The only case left to check is when n is odd and C_{i−1}C_{j−1}C_{k−1} ≡_{4} 2. In this case, by induction n = 2 · 2^{b} + (2^{c} + 2^{d}) with b, c, d ≥ 0 and d > c. Since n is odd then c = 0, so that n − 2 = 2^{b+1} + 2^{d} − 1.

(c) Suppose 2nC_{i}C_{j}C_{k} ≢_{4} 0. Since C_{i}, C_{j} and C_{k} are odd, n = 2^{b} + 2^{c} + 2^{d} for some d > c > b ≥ 0. Since n is odd, b = 0 and n − 2 = 2^{c} + 2^{d} − 1.

Another congruence relation follows immediately from reducing (2) modulo a prime p ≥ 5.

Theorem 4. If p ≥ 5 is prime and n ≡_{p} −2 then C_{n} ≡_{p} 0.

3 Generalization to k-angulations

Lemma 1 can be generalized to give a recursion for the number of k-angulations, which are partitions of a polygon into k-gons. Let f_{n,k} be the number of k-angulations of an n-gon. It is well known (see, for example, the paper of Przytycki and Sikora [5]) that

f_{(k−1)n+2,k+1} = C_{n,k}  (8)

where

C_{n,k} = \frac{1}{(k − 1)n + 1}\binom{kn}{n}

are the k-Catalan numbers [7, A137211]. Define f_{n,k} = 0 unless n = (k − 2)m + 2 for some integer m ≥ 0. The proof of the following Lemma is completely analogous to that of Lemma 1.

Lemma 5. For any n ≥ 2 and k ≥ 3,

f_{n,k} = \frac{n}{2}f_{n/2+1,k}^{2} + ∑_{\begin{matrix}i_{1}+...+i_{k}=n \\ i_{1}≤...≤i_{k}<n/2 \end{matrix}} m_{i_{1}...i_{k}}f_{i_{1}+1,k} ⋯ f_{i_{k}+1,k},  (9)

where m_{i_{1}...i_{k}} is the number of ways to position a k-gon with sides of cyclic lengths i_{1}, …, i_{k} inside an N-gon for N = i_{1} + … + i_{k}.

For example, let

Q_{n} = \frac{1}{2n + 1}\binom{3n}{n}

be the number of quadrangulations of a (2n+2)-gon, and let Q_{x} = 0 unless x is a nonnegative integer. Then

Q_{n} = (n + 1)Q_{n/2}^{2} + ∑_{\begin{matrix}i+j+k+l=2n+2 \\ i≤j≤k≤l<n+1 \end{matrix}} m_{ijkl}Q_{(i−1)/2}Q_{(j−1)/2}Q_{(k−1)/2}Q_{(l−1)/2},  (10)

where

m_{ijkl} = \begin{cases}\frac{N}{4} , & if i = l; \\ N, & if i = k < l or i < j = l; \\ \frac{3N}{2} , & if i = j < k = l; \\ 3N, & if i = j < k < l or i < j = k < l or i < j < k = l; \\ 6N, & if i < j < k < l \end{cases}  (11)

for N = i + j + k + l.

Theorem 4 can be generalized by reducing equation (9) modulo a prime p ≥ 3.

Theorem 6. If p ≥ 3 is prime with p |̸k and p|n then f_{n,k} ≡_{p} 0.

Proof. For a given k-gon, the number of cyclic permutations of the k sides that leave the k-gon unchanged is divisible by k. Therefore the number of inequivalent rotations of the k-gon inside the n-gon is divisible by n/k. It follows that m_{i_{1}...i_{k}} is divisible by n/k, and so the given assumptions imply that p divides f_{n,k}.

4 Triangulations with a fixed vertex in their central component

L. Shapiro [6] proposed the following question: how many triangulations include the vertex 0 in their central component? The following theorem answers this question.

Theorem 7. Let n ≥ 3. The number f(n) of triangulations of an n-gon with the vertex 0 outside their central component is

f(n) = \frac{1}{2}C_{n−1} − C_{n−2} + \frac{1}{2}C_{n/2−1}^{2}.

Proof. Enumerate these triangulations according to the cyclic length l of the shortest diagonal that separates 0 form the center (see Figure 2).

Given such l, suppose this diagonal is given by k(n + k − l). Note that 1 ≤ k ≤ l − 1. Since this is the shortest such diagonal, the triangulation must also include the diagonals 0k and 0(n + k − l), forming a triangle. The regions outside of this triangle can be triangulated arbitrarily. Therefore

f(n) = ∑_{l=2}^{⌊n/2⌋} ∑_{k=1}^{l−1} C_{n−l−1}C_{l−k−1}C_{k−1}

= ∑_{l=2}^{⌊n/2⌋} C_{n−l−1}C_{l−1}

= ∑_{m=1}^{⌊n/2⌋−1} C_{m}C_{n−2−m}

= \frac{1}{2} ∑_{m=1}^{n−3} C_{m}C_{n−2−m} + \frac{1}{2}C_{n/2−1}^{2},

where the second equality follows from (1). The result now follows by again applying (1).

Figure 2: Triangulations with the vertex 0 outside the central component.

It seems that the sequence a(n) = f(n − 3) is given in an entry of Sloane’s encyclopedia [7, A027302]:

a(n) = ∑_{0≤k<n/2} T (n, k)T (n, k + 1),

where

T (n, k) = \frac{n − 2k + 1}{n − k + 1}\binom{n}{k}.

In this entry it also asserted that a(n) is the number of Dyck (n + 2)-paths with UU spanning their midpoint. It would be interesting to determine whether any known bijection between triangulations and Dyck paths gives this correspondence.

References

[1] R. Alter and K. Kubota, Prime and prime power divisibility of Catalan numbers, J. Combin. Theory Ser. A 15 (1973), 243–256.

[2] D. Bowman and A. Regev, Counting symmetry classes of dissections of a convex regular

    polygon, preprint, http://arxiv.org/abs/1209.6270.

[3] E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[4] S. Eu, S. Liu, and Y. Yeh, Catalan and Motzkin numbers modulo 4 and 8, European J. Combin. 29 (2008), 1449–1466.

[5] J. H. Przytycki and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman and Cayley numbers, J. Comb. Theory A 92 (1) (2000), 68–76.

[6] L. Shapiro, Private communication, 2012.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[8] G. Xin and J. Xu, A short approach to Catalan numbers modulo 2^{r}, Electron. J. Combin. 18 (2011), P177.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A10. Keywords: Catalan numbers, polygon triangulation, polygon dissection, congruence.

(Concerned with sequences \underline{A000108}, \underline{A137211}, and \underline{A027302}.)

Received October 21 2012; revised version received March 1 2013. Published in Journal of Integer Sequences, March 9 2013.

Return to Journal of Integer Sequences home page.