Number of Dissections of the Regular n-gon by Diagonals

Joris N. Buloron, Roberto B. Corcino, and Jay M. Ontolan Cebu Normal University Cebu City, Philippines

                    jorisbuloron@yahoo.com

Abstract This paper presents a formula for the distinct dissections by diagonals of a regular n-gon modulo the action of the dihedral group. This counting includes dissection with intersecting or non-intersecting diagonals. We utilize a corollary of the Cauchy-Frobenius theorem, which involves counting of cycles. We also give an explicit formula for the prime number case. We give as a remark the number of distinct dissections, modulo the action of the cyclic group of finite order.

1 Introduction

The theory of polygon dissection has proven to be a rich area of mathematical thoughts. Cayley derived the number of ways to dissect an n−gon using a specified number of diagonals. Other mathematicians gave proofs of older formulas involving polygon dissections using new techniques, such as generating functions, Legendre polynomials, and Lagrange inversion [2]. Przytycki and Sikora showed relationships between polygon dissections and special types of numbers, such as the Catalan numbers [4]. Explicit formulas for dissections of a regular polygon using non-intersecting diagonals were derived in a paper of Bowman and Regev [1]. More recently, Siegel counted the number of dissections of a regular n-gon using nonintersecting diagonals in his thesis [5].

The main aim of this paper is to count the number of distinct dissections of an unlabeled regular n-gon by diagonals modulo the dihedral group. We consider both intersecting and non-intersecting diagonals in our counting. To do this, we first label the vertices of the polygon and determine which dissections of this labeled n-gon are the same up to the canonical action of the dihedral group of degree n. We present the following definition:

Definition 1. Let n ≥ 3. A regular polygon with n vertices is called an n-gon. A diagonal of an n-gon is a segment extending from a vertex to a non-adjacent vertex. A dissection of the n-gon is any set of crossing or non-crossing diagonals of the n-gon. A dissection without any diagonal is an empty dissection.

The main result of this paper is anchored on a consequence of the Cauchy-Frobenius theorem [3, Corollary 1.7A, p. 26]. We give it below as Lemma 2.

Lemma 2. Let G be a finite group acting on a finite set Δ. Suppose Γ is a non-empty finite set and Fun(Δ, Γ) is the set of all functions from Δ to Γ, then G acts on Fun(Δ, Γ) by

f^{x}(δ) = f(δ^{x^{−1}}) (∀f ∈ Fun(Δ, Γ), x ∈ G, δ ∈ Δ.)

In addition, the number of orbits of this action is equal to

\frac{1}{|G|} (∑_{g∈G} |Γ|^{c(g)})

where c(g) counts the number of cycles of g as it acts on Δ, including the trivial cycles, if they exist.

2 Preliminaries

Let [n] = {1, 2, …, n} be the set of vertices of a regular n-gon. It is well-known that the dihedral group of degree n, with presentation D_{n} = ⟨r, s : r^{n} = 1 = s^{2}, srs = r^{−1}⟩, acts on [n] in a natural way. This is obvious when we express the elements of D_{n} as permutations of [n] corresponding to the symmetries of an n-gon, i.e., D_{n} ≤ Sym([n]). Here, r is the \frac{2π}{n}-rotation and s is the reflection along the axis through center and vertex 1.

Definition 3. Let i, j ∈ [n] be vertices of the n-gon. If i < j, then we define the cycle length of i and j as follows:

d({i, j}) = min {j − i, n − (j − i) mod n} .

Form Δ_{n} = {{i, j} : d({i, j}) ≥ 2}. This is simply the set of all diagonals of the n-gon and it can be shown that |Δ_{n}| = \frac{n^{2}−3n}{2}. Moreover, the group D_{n} acts on Δ_{n} in a natural way. Observe that {i, j} ∈ Δ_{n} if and only if i and j are non-adjacent. Since each element of D_{n} only rotates or reflects the n-gon, then for x ∈ D_{n}

d({i^{x}, j^{x}}) = d({i, j}).

It can then be proven that the map Δ_{n} × D_{n} → Δ_{n} defined by

{i, j}^{g} = {i^{g}, j^{g}}

is an action. Let us denote the corresponding permutation representation of this action by ρ : D_{n} → Sym(Δ_{n}). That is, ρ(r) and ρ(s) are permutations of the set Δ_{n} satisfying the following:

i. ρ(r)({i, j}) = {i + 1 mod n, j + 1 mod n};

ii. ρ(s)({i, j}) = {2 − i mod n, 2 − j mod n}.

Consider the family Fun(Δ_{n}, Γ) where Γ = {0, 1}. We can view each function f ∈ Fun(Δ_{n}, Γ) as a way of dissecting the n-gon. Here, f({i, j}) = 1 means that there exists a diagonal from vertex i to j. Otherwise, i and j are not connected by any diagonal. The action of an element x ∈ D_{n} on Fun(Δ_{n}, Γ) can be viewed as either rotating or reflecting the dissection f to f^{x} preserving the form of the dissection. Consequently, every orbit of this action represents a certain way of dissecting an n-gon. This only means that counting the distinct orbits is equivalent to counting the number of distinct dissections of the n-gon modulo the dihedral group.

Proposition 4. The number γ(n) of distinct dissections of an n-gon modulo the dihedral action is

γ(n) = \frac{1}{2n} ( ∑_{g∈D_{n}} 2^{c(g)})

where c(g) counts the number of cycles of g as it acts on Δ_{n}, including the trivial cycles whenever they exist.

3 Result

The following observation will be used to prove the succeeding claims:

Proposition 5. Let n > 4 be a natural number. Then ρ[D_{n}] ≅ D_{n}.

Proof. Let r, s be the generators of D_{n}. When we express ρ(r) as a product of disjoint cycles, we see that ({1, 3} {2, 4} {3, 5} … {n − 1, 1} {n, 2}) is one of these cycles. Since this cycle is of length n and |ρ(r)| ≤ n, then the length of each cycle is at most n and so |ρ(r)| = n.

We now show that |ρ(s)| = 2. Since |s| = 2, then |ρ(s)| divides 2 and so the length of each cycle is at most two. If n is odd then ρ(s) sends \{1, \frac{n+1}{2}\} to \{1, \frac{n+3}{2}\} and this creates a cycle of length two. If n is even, ρ(s) sends \{1, \frac{n}{2}\} to \{1, \frac{n+4}{2}\} and again, this makes a cycle of length two. Hence, |ρ(s)| = 2.

Finally, we obtain

ρ(s)ρ(r)ρ(s) = ρ(srs) = ρ(r^{−1}) = ρ(r)^{−1}.

For x ∈ D_{n}, we now count the number of cycles in the decomposition of ρ(x). We make use of the well-known properties of permutations stated as Lemma 6. Lemma 6. Let α ∈ Sym([n]) such that α = c_{1}c_{2} ⋯ c_{l}, where c_{i}’s are disjoint cycles, then

|α| = lcm(length(c_{i}) : i ∈ {1, 2, …, l}).

If α = (a_{1} a_{2} … a_{k}), then the number of disjoint cycles of α^{t}, where 1 ≤ t ≤ k, is gcd(k, t).

Lemma 7. Let n ≥ 4. For i ∈ {1, 2, …, n},

c(r^{i}) = \begin{cases}(\frac{n−4}{2}) gcd(n, i) + gcd(\frac{n}{2}, i), & if n is even; \\ (\frac{n−3}{2}) gcd(n, i), & if n is odd. \end{cases}

Proof. We start with n = 4. Then Δ_{4} = {{1, 3} , {2, 4}}, i ∈ {1, 2, 3, 4} and we obtain the following computations: i = 1. ρ(r) = (\{1, 3\} \{2, 4\}) and so c(r) = 1 = (\frac{4−4}{2}) gcd(4, 1) + gcd(\frac{4}{2}, 1); i = 2. ρ(r^{2}) = (\{1, 3\}) (\{2, 4\}) = 1_{Δ_{4}} and so c(r^{2}) = 2 = (\frac{4−4}{2}) gcd(4, 2) + gcd(\frac{4}{2}, 2); i = 3. ρ(r^{3}) = (\{1, 3\} \{2, 4\}) and so c(r^{3}) = 1 = (\frac{4−4}{2}) gcd(4, 3) + gcd(\frac{4}{2}, 3); i = 4. ρ(r^{4}) = ρ(1_{[4]}) = 1_{Δ_{4}} = (\{1, 3\}) (\{2, 4\}) and so c(r^{4}) = 2 = (\frac{4−4}{2}) gcd(4, 4) + gcd(\frac{4}{2}, 4).

We let n > 4 and consider two cases. Firstly, assume n is even. The elements of Δ_{n} can be partitioned according to different cycle lengths and we get the following cycle decomposition:

ρ(r) = \underbrace{(\{1, 3\} \{2, 4\} … \{n, 2\})}_{n−cycle} \underbrace{(\{1, 4\} \{2, 5\} … \{n, 3\})}_{n−cycle} …

\underbrace{(\{1, n/2\} \{2, (n + 2)/2\} … \{n, (n − 2)/2\})}_{n−cycle} \underbrace{(\{1, (n + 2)/2\} \{2, (n + 4)/2\} … \{n/2, n\})}_{n/2−cycle}

in which there are \frac{n−4}{2} n-cycles and only one \frac{n}{2}-cycle. For i ∈ \{1, 2, …, n\}:

ρ(r^{i}) = ({1, 3} {2, 4} … {n, 2})^{i} ({1, 4} {2, 5} … {n, 3})^{i} …

({1, n/2} {2, (n + 2)/2} … {n, (n − 2)/2})^{i} ({1, (n + 2)/2} {2, (n + 4)/2} … {n/2, n})^{i} . By Lemma 6, we obtain

c(r^{i}) = (\frac{n − 4}{2}) gcd(n, i) + gcd(n/2, i).

Secondly, take n to be odd. Similar to the first case, the elements of Δ_{n} can be partitioned according to different cycle lengths. We obtain the following:

ρ(r) = \underbrace{(\{1, 3\} \{2, 4\} … \{n, 2\})}_{n−cycle} \underbrace{(\{1, 4\} \{2, 5\} … \{n, 3\})}_{n−cycle} …

\underbrace{(\{1, (n + 1)/2\} \{2, (n + 3)/2\} … \{n, (n − 1)/2\})}_{n−cycle}

in which there are \frac{n−3}{2} n-cycles. As with the above, we can compute the following:

c(r^{i}) = (\frac{n − 3}{2}) gcd(n, i).

Lemma 8. Let n ≥ 4 and s_{v} ∈ D_{n}\⟨r⟩ be a reflection with axis passing through the center and a vertex. Then

c(s_{v}) = \begin{cases}\frac{n^{2}−2n}{4}, & if n is even; \\ \frac{n^{2}−2n−3}{4}, & if n is odd. \end{cases}

Proof. Note that the case n = 4 is an easy computation. We consider two cases for n > 4. Firstly, take n to be even. The axis of s_{v} is the diagonal \{i, i + \frac{n}{2} mod n\}. Form

Δ_{o} = \{\{i − k mod n, i + k mod n\} : k ∈ \{1, 2, …, \frac{n − 2}{2}\}\} .

Observe that (i ± k mod n)^{s_{v}} = i ∓ k mod n and preserves both i and i + \frac{n}{2} mod n. This implies that s_{v} fixes setwise each element of Δ_{o} ∪ \{\{i, i + \frac{n}{2} mod n\}\}. Let \{α, β\} be an element of Δ_{n}\ (Δ_{o} ∪ \{\{i, i + \frac{n}{2} mod n\}\}), we consider three subcases. Let α = i. It follows that β ∈ \{i ± k mod n : k ∈ \{2, …, \frac{n−2}{2}\}\}. If β = i + k mod n then \{i, i + k mod n\}^{s_{v}} = {i, i − k mod n}. If β = i − k mod n then {i, i − k mod n}^{s_{v}} = {i, i + k mod n}. Similar argument when α = i+\frac{n}{2} mod n. Suppose \{α, β\}∩\{i, i + \frac{n}{2} mod n\} = ∅. It implies that α, β ∈ \{i ± k mod n : k ∈ \{1, 2, …, \frac{n−2}{2}\}\}. If α = i+k_{1} mod n and β = i+k_{2} mod n where k_{1}, k_{2} ∈ \{1, 2, …, \frac{n−2}{2}\}, then \{i + k_{1} mod n, i + k_{2} mod n\}^{s_{v}} = \{i − k_{1} mod n, i − k_{2} mod n\}. Similar argument can be used for α = i − k_{1} mod n and β = i − k_{2} mod n. Without loss of generality, assume α = i − k_{1} mod n and β = i + k_{2} mod n. It means that k_{1} ≠ k_{2} and so {i − k_{1} mod n, i + k_{2} mod n}^{s_{v}} = {i + k_{1} mod n, i − k_{2} mod n}. In all these subcases, we obtain {α, β}^{s_{v}} ≠ {α, β}.

Proposition 5 and Lemma 6 assure that the length of every cycle in ρ(s_{v}) is at most two. The above results tell us that each element of Δ_{o} ∪ \{i, i + \frac{n}{2} mod n\} creates an 1-cycle in ρ(s_{v}), while each element of Δ_{n}\ (Δ_{o} ∪ \{i, i + \frac{n}{2} mod n\}) creates a 2-cycle. Hence,

c(s_{v}) = \frac{n^{2} − 2n}{4}.

For the second case, assume n is an odd integer. The axis of s_{v} is the segment extending from vertex i to the midpoint of the edge {i + (n − 1)/2 mod n, i − (n − 1)/2 mod n}. Form

Δ_{o} = \{\{i + k mod n, i − k mod n\} : k ∈ \{1, 2, …, \frac{n − 1}{2}\}\} .

Observe that i^{s_{v}} = i and (i ± k mod n)^{s_{v}} = i ∓ k mod n. Thus, each element of

Δ_{o}\ \{\{i + \frac{n − 1}{2} mod n, i − \frac{n − 1}{2} mod n\}\}

creates an 1-cycle in ρ(s_{v}). Let {α, β} ∈ Δ_{n}\Δ_{o}. We consider two subcases. Without loss of generality, assume α = i. It follows that β ∈ {i ± k mod n : k ∈ {2, …, (n − 1)/2}} and either {i, i + k mod n}^{s_{v}} = {i, i − k mod n} or {i, i − k mod n}^{s_{v}} = {i, i + k mod n}. Let i ∉ {α, β}. It means that α, β ∈ {i ± k mod n : k ∈ {1, 2, …, (n − 1)/2}}. As with the above, we always obtain {α, β}^{s_{v}} ≠ {α, β} in different subcases.

Since the length of each cycle of ρ(s_{v}) is at most two, then the two subcases above imply that every {α, β} ∈ Δ_{n}\Δ_{o} creates a 2-cycle in ρ(s_{v}). Hence,

c(s_{v}) = \frac{n^{2} − 2n − 3}{4}.

Lemma 9. Let n ≥ 6 be even. Suppose s_{e} ∈ D_{n}\⟨r⟩ to be a reflection with axis passing through the origin and midpoints of opposing edges. Then

c(s_{e}) = \frac{n^{2} − 2n − 4}{4}

Proof. The axis of s_{e} is the segment extending from the midpoint of an edge {i, i + 1 mod n} to the midpoint of \{i − (\frac{n}{2} − 1) mod n, i + \frac{n}{2} mod n\}. We note that for j ∈ [n], j^{s_{e}} = (2i + 1) − j mod n. Let

Δ_{o} = {{i + k mod n, i − k + 1 mod n} : k ∈ {2, 3, …, (n − 2)/2}} .

It should be noted that s_{e} fixes setwise each element of Δ_{o} and creates an 1-cycle in ρ(s_{e}).

For \{α, β\} ∈ Δ_{n}\Δ_{o}, there exists k ∈ \{1, 2, …, \frac{n}{2}\} such that if α = i + k mod n, then β ∈ [n]\ {i + k mod n, i − k + 1 mod n} and so

{i + k mod n, β}^{s_{e}} = {i − k + 1 mod n, β^{s_{e}}} ≠ {α, β} .

Also, if α = i − k + 1 mod n then β ∈ [n]\ {i + k mod n, i − k + 1 mod n} and so

{i − k + 1 mod n, β}^{s_{e}} = {i + k mod n, β^{s_{e}}} ≠ {α, β} .

Hence, each element of Δ_{n}\Δ_{o} creates a 2-cycle of ρ(s_{e}). That is,

c(s_{e}) = \frac{n^{2} − 2n − 4}{4}.

We now collect the properties from Lemmas 7, 8 and 9 and plug them in to the equation in Proposition 4 to obtain our main result.

Theorem 10. Let n ≥ 3. The number γ(n) of distinct ways of dissecting an n-gon modulo the action of the dihedral group D_{n} is:

γ(n) = \begin{cases}\frac{1}{2n} (( n ; ∑_{i=1}2^{(^{\frac{n−4}{2}}) gcd(n,i)+gcd( \frac{n}{2} ,i)}) + \frac{n}{2} (2^{\frac{n^{2}−2n}{4}} + 2^{\frac{n^{2}−2n−4}{4}} )) , & if n is even; \\ \frac{1}{2n} (( n ; ∑_{i=1}2^{(^{\frac{n−3}{2}}) gcd(n,i)}) + n (2^{\frac{n^{2}−2n−3}{4}} )) , & if n is odd. \end{cases}

Corollary 11. The number of dissections of a regular p-gon modulo the dihedral action, where p is prime with p ≥ 3, is

\frac{(p − 1) · 2^{\frac{p−3}{2}} + 2^{\frac{p^{2}−3p}{2}} + p · 2^{\frac{p^{2}−2p−3}{4}}}{2p} .

4 Remark

The number γ_{c}(n) of distinct ways of dissecting an n-gon modulo the action of the cyclic group ⟨(1 2 … n)⟩ is

γ_{c}(n) = \begin{cases}\frac{1}{n} ( n ; ∑_{i=1}2^{(^{\frac{n−4}{2}}) gcd(n,i)+gcd( \frac{n}{2} ,i)}) , & if n is even; \\ \frac{1}{n} ( n ; ∑_{i=1}2^{(^{\frac{n−3}{2}}) gcd(n,i)}) , & if n is odd. \end{cases}

Moreover, when n = p ≥ 3, then

γ_{c}(p) = \frac{(p − 1) · 2^{\frac{p−3}{2}} + 2^{\frac{p^{2}−3p}{2}}}{p} .

5 Acknowledgment

The authors would like to thank Cebu Normal University for its support while the research was being undertaken, and Professor Romola Savellon for the grammar review.

References

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

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

[2] D. Callan, Polygon dissections and marked Dyck paths, preprint, 2005,

   https://pdfs.semanticscholar.org/d405.

[3] J. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, 1996.

[4] J. Przytycki and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman and Cayley

   numbers, preprint, 1998, https://arxiv.org/abs/math/9811086.

[5] A. Siegel, Counting the number of distinct dissections of a regular n-gon, thesis, University of Akron, 2014.

2010 Mathematics Subject Classification: Primary 05C25; Secondary 05C69. Keywords: n-gon, dissection, dihedral group.

Received September 13 2016; revised version received May 9 2016; June 30 2017; July 18 2017. Published in Journal of Integer Sequences, July 29 2017. Minor revision, August 14 2017.

Return to Journal of Integer Sequences home page.