Enumeration of Vertices, Edges and Polygons in Tessellations of the Plane

Marcelo Firer Imecc — Unicamp

Rua Sérgio Buarque de Holanda 651

13083-859 Campinas — SP

Brazil

mfirer@ime.unicamp.br

Karine Bobadilha Couto Fatec — Catanduva Rua Maranhão 898

15800-020 Catanduva — SP

Brazil

karinebobadilha@yahoo.com.br

Eduardo Brandani da Silva^{1} Department of Mathematics Maringa State University

Av. Colombo 5790 Maringa, PR

Brazil

ebsilva@wnet.com.br

Abstract

In this work, we consider the tessellations (or tilings) of Euclidean and hyperbolic planes using copies of a regular polygon. We introduce the concept of k-type of vertices and edges, which allow a thorough control of these elements when the tessellation increases, and we obtain an enumeration for the vertices, edges, and polygons at a given distance.

1Partially funded by a grant from Fapesp (2014/25463-6).

1 Introduction

In this study, we investigate regular infinite tessellations of the Euclidean or hyperbolic plane and the Coxeter group G generated by the set S of reflections on the edges of a fundamental polygon Δ of the tessellation. Considering the Cayley metric d(·, ·) of the group (G, S), we denote by ∥g∥ = d(g, e) the norm of an element g ∈ G. For a given positive integer n we consider the image of Δ under the n-ball,

B_{n}(Δ) = {g(Δ); ∥g∥ ≤ n},

and ask the following natural questions:

1. How many faces (polygons) are there in B_{n}(Δ)?

2. How many polygons edges are there in B_{n}(Δ)?

3. How many polygons vertices are there in B_{n}(Δ)?

The first question is equivalent to asking about the growth sequence {P_{n}} of the Coxeter group (G, S), and the answer is known: The generating function of this sequence is rational. We can obtain an explicit formula given in terms of the Coxeter presentation.

This particular (but quite general) situation arises when we consider the elements of a group (or semi-group) G acting as isometries of a metric space (X, d), an instance that is the most general formulation of a dynamical system. In such a theoretical group setting, a survey, conducted by Grigorchuk and De La Harpe in 1997 [7], explored many aspects of the growth problem and provided references to the growth of other objects. In a particular case in which G is an infinite Coxeter (or Artin) group generated by a set S of reflections (characterized as a simple set of roots), there is a formal power series ∑_{n=0}^{∞} a_{n}t^{n}, where the coefficient a_{n} denotes the number of elements within distance n from the identity element. Cannon [4, 5] also considered the growth series of tessellations related to the surfaces of genus g ≥ 2, which do not include all possible tessellations of the hyperbolic plane. These results were generalized by Floyd and Plotnik [6] and Bartholdi and Ceccherini-Silberstein [2], who considered more general tessellations.

Counting vertices is a dual problem: Counting the vertices of a {p, q} tesselation (a tesselation through regular p-gons with inner angles equal to 2π/q) is equivalent to counting the number of polygons on a {q, p} tesselation.

To date, the second question posed above, when counting the edges of these tessellations, has yet to be answered. We use a geometric approach, similar to the one adopted by Silva et al. [9] in a simpler situation, which allows us to answer the three questions, by giving a recursive definition of those quantities. The involved part of the counting process is avoiding repetitions, and the key results that enabling us to develop recursive formulae are found in Propositions 1 and 2.

To obtain our results, we introduced the notion of “k-type” of vertices and edges, which allows us to receive very precise information on the behavior of their growth. In addition to obtaining the total amount of these elements, we have a clear way of numbering them from one level to the next. As another important point, we obtain the number of vertices and polygons as a function of the number of edges. This type of relationship has not been shown before.

Such approach can have applications in the natural sciences and computer science, and has several interpretations and meanings in mathematics. The results obtained also have applications in communication theory. A signal constellation is a finite subset of points with suitable geometric properties, and the choice of the set to be used in the design of such a system plays a fundamental role, mainly because the performance of the system is dependent on the signal constellation. Signal constellation are usually built up from a lattice A in ℝ^{n}, which becomes a signal constellation, after taking a convenient quotient using a sublattice A′ ⊂ A. One of the most important of such possibilities is considering the constellations of points in the hyperbolic plane. Silva et al. [10] introduced a proposal for new communication systems in a hyperbolic context. The main potential for coding in the hyperbolic plane is the infinitude of essentially distinct tessellations, in contrast to a Euclidean case. Not only can we find infinite constellations, we can also find an infinite number of properly discontinuous groups of isometries that are not isomorphic (as abstract subgroups) to each other. Moreover, because rigidity (in the sense of Mostow) does not hold in the (two-dimensional) hyperbolic plane, for each co-compact properly discontinuous group of isometries F, there are an uncountable number of subgroups isomorphic to F, albeit not conjugated to it. In other words, for every such subgroup, there is a situation similar to the essentially unique situation found in ℝ^{n}.

Albuquerque et al. [1] obtained new quantum error correcting codes by using hyperbolic geometry. The precise control given by the results of this paper can be useful in such contexts, because this type of information is fundamental to calculating the performance in border points of signal constellations. Finally, we should mention that Ungerboeck [12] introduced a very important modulation technique for communication systems using a Euclidean case of the sets considered here.

2 Growth of hyperbolic tessellations

Let us consider in the hyperbolic plane ℍ^{2} a regular polygon P_{p,q} that has p equal-length edges, and where all p internal angles are equal \frac{2π}{q}. From Poincaré’s theorem, such polygons exist for all positive integers p and q whenever \frac{1}{p} + \frac{1}{q} < \frac{1}{2}. The above is assumed as a basic condition throughout the current research. It is possible to tile ℍ^{2} with P_{p,q}, in the sense that there is a family {P_{n}|n ∈ ℕ} of isometric copies of P_{p,q}, such that ℍ^{2} = ∪_{n∈ℕ}P_{n}. When P_{n} ∩ P_{m} ≠ ∅, this intersection is either a common edge or a common vertex. We say that the family T_{p,q} = {P_{n}|n ∈ ℕ} defines a tessellation (or tiling) and each P_{n} is called a tile. An edge (vertex) of a tessellation is an edge (vertex) of a tile. We denote the set of edges and vertices of T_{p,q} by E_{p,q} and V_{p,q}, respectively. See Beardon [3] for more details about hyperbolic geometry. We should note that the results in this paper are also valid in the Euclidean case where regular tessellations satisfy \frac{1}{p} + \frac{1}{q} = \frac{1}{2}. Thus, we use the term “tessellation of the plane” to include both the Euclidean and hyperbolic cases.

There is a natural metric associated to such tiling. Given tiles P and P′, we consider points x and x′ contained in the interior of the tiles. Let γ be a path connecting the given points, that is, γ : [0, 1] → ℍ^{2} is a continuous map, such that γ(0) = x and γ(1) = x′. If no vertex of the tiling is contained in the image of γ, we say that γ is a regular path. Let |γ| be the number of edges of the tilling crossed by γ:

|γ| := |{ε ∈ E_{p,q} | ε ∩ γ([0, 1]) ≠ ∅}| ,

where |X| throughout the current paper denotes the cardinality of the set X. We define

d(P, P′) := inf{|γ | γ is a regular path connecting x to x′}
= min{|γ | γ is a regular path connecting x to x′}.

The above defines a metric in a set of tiles. It is well known that the tiling T_{p,q} has exponential growth, that is, there are constants M, α ∈ ℝ, b ∈ ℕ with M, α > 0, b > 1, such that

0 < lim_{n→∞} \frac{| B_{n}(P)|}{Mb^{αn}} < ∞ ,

where B_{n}(P) = {P′ ∈ T_{p,q} : d(P, P′) ≤ n} is the ball (in T_{p,q}) centered on P, with radius n (see Sullivan [11, Proposition 3]).

Let Δ_{0} be the initial tile of our tessellation, and p_{0} be its barycenter. The geodesics of ℍ^{2}, containing the edges of Δ_{0}, are called support geodesics of the tile. Each geodesic δ_{i}, i = 1, …, p determines a unique reflection ρ_{i} (involutive isometry of ℍ^{2} that has the geodesic as a set of fixed points). We let Γ_{p,q} denote the group generated by {ρ_{1}, …, ρ_{p}}. The group Γ_{p,q} is a discrete group of isometries that has Δ_{0} as a fundamental Dirichlet domain centered at p_{0}, and thus

Δ_{0} = {x ∈ ℍ^{2} | d(x, p_{0}) ≤ d(f(x), p_{0}), ∀f ∈ Γ_{p,q}} ,

and every tile Δ_{n} ∈ T_{p,q} is an image f(Δ_{0}) for a unique f ∈ Γ_{p,q}. If we consider the Cayley metric d_{C}(·, ·) on Γ_{p,q} determined by the set {ρ_{1}, …, ρ_{p}} of generators, we find that

d(f(Δ_{0}), h(Δ_{0})) = d_{C}(f, h), ∀f, h ∈ Γ_{p,q}.  (1)

We will now introduce a few concepts and definitions. We consider the set of reflections at the edges of the regular polygon Δ_{0} (with p edges and angles equal to \frac{2π}{q}) as a standard set of generators of the group Γ_{p,q}. A geodesic δ is a support geodesic of the tessellation if an edge of a tile of the tessellation T_{p,q} is contained in δ. Let S be the set of all support geodesics, and δ ∈ S if, and only if, ρ_{δ} is a reflection contained in the group Γ_{p,q}.

Because d(g(Δ_{0}), h(Δ_{0})) = d_{C}(g, h), ∀g, h ∈ Γ_{p,q}, we can consider metric constructions in T_{p,q} or in Γ_{p,q} without a distinction.

Let B_{k} be the closed ball in Γ_{p,q} with the center in the identity and radius k, and let C_{k} := B_{k} \ B_{k−1} be the circumference of radius k, which we call the k-th stage (level) of the tessellation, that is, B_{k} := {g ∈ Γ_{p,q} | d_{C}(g, e) ≤ k} and C_{k} := {g ∈ Γ_{p,q} | d_{C}(g, e) = k}.

From the correspondence between the elements of the group and the polygons of the tessellation, we let P_{k} denote the set of polygons of the tessellation corresponding to the ball B_{k} in the group, and by NP_{k} := P_{k} \ P_{k−1} the set corresponding to the circumference C_{k}, where the prefix N stands for new: P_{k} = {g(Δ_{0}) | g ∈ B_{k}} and NP_{k} = {g(Δ_{0}) | g ∈ C_{k}}.

Naturally, we have | P_{k} | = | B_{k} |, | NP_{k} | = | C_{k} | where | P_{k} |, the cardinality of P_{k}, is the k-th coefficient of the growth series of the group Γ_{p,q}. Our goal is to obtain a recursive enumeration for P_{k}, and, to attain this objective, we determine the growth of the vertices and edges of the polygons. We let V_{k} denote the set of vertices of polygons in P_{k}, and E_{k} denote the set of edges of polygons in P_{k}. In a similar way, we let NE_{k} := E_{k} \ E_{k−1} and NV_{k} := V_{k} \ V_{k−1} denote the sets of the new vertices and edges in the tessellation, respectively. Clearly, we then have

| V_{k} | = ∑_{i=0}^{k} | NV_{i} |, | E_{k} | = ∑_{i=0}^{k} | NE_{i} | and | P_{k} | = ∑_{i=0}^{k} | NP_{i} | ,  (2)

where | NV_{0} | = | NE_{0} | = p and | NP_{0} | = 1. Therefore, it is sufficient to know | NP_{k} | to determine the cardinality of the balls in the group Γ_{p,q}.

Considering the polygons in P_{k−1}, we have only one way to obtain new polygons in stage k: The reflections in the edges of the polygons in P_{k−1}. We observe that ε ∈ E_{k−1} is an edge of either one or two polygons in P_{k−1}: If ε is an edge of only one polygon Δ ∈ P_{k−1}, we have ρ_{ε}(Δ) (the reflection of the polygon Δ in the edge ε) is a new polygon in NP_{k}; whereas if ε is an edge of two polygons in P_{k−1}, the reflection ρ_{ε} only permutes those tiles, and does not give rise to any new element in P_{k}. If edge ε in E_{k−1} is an edge of only one polygon, then ε ∈ NE_{k−1}.

We define the function t_{k} : V_{k} → {2, …, q}, which for each vertex v ∈ V_{k} gives the number of edges of E_{k} that have v as a vertex. We state t_{k}(v) is the k-type of vertex v, and the notation v_{k}^{w} is used to state that w = t_{k}(v). We also need the following notation:

V_{k} = {v_{k,1}^{w_{1}}, v_{k,2}^{w_{2}}, …, v_{k,| V_{k} |}^{w_{| V_{k} |}}} and NV_{k} = {v_{k,1}^{w_{1}}, v_{k,2}^{w_{2}}, …, v_{k,| NV_{k} |}^{w_{| NV_{k} |}}},

where k is the stage of the tessellation, and w_{i} = t_{k}(v_{k,i}), with i = 1, …, | V_{k} | for V_{k}, and i = 1, …, | NV_{k} | for NV_{k}.

Considering an edge ε ∈ E_{k}, we characterize it using the k-type of both its vertices: We state that ε has k-type (t_{k}(ι(ε), t_{k}(τ(ε)))), where ι(ε) and τ(ε) are the initial and final vertices, respectively, which determine ε. It is assumed that t_{k}(ι(ε)) ≤ t_{k}(τ(ε)), and, without ambiguity, we can assume the notation ε_{k}^{i_{j},w_{j}}, where i_{j} = t_{k}(ι(ε)) and w_{j} = t_{k}(τ(ε)), with j = 1, …, | E_{k} | for E_{k} and j = 1, …, | NE_{k} | for NE_{k}. As in the case of the vertices, we use the following notation for the set of edges at a given level k:

E_{k} = {ε_{k,1}^{i_{1},w_{1}}, ε_{k,2}^{i_{1},w_{1}}, …, ε_{k,| E_{k} |}^{i_{| E_{k} |},w_{| E_{k} |}}}; NE_{k} = {ε_{k,1}^{i_{1},w_{1}}, ε_{k,2}^{i_{2},w_{2}}, …, ε_{k,| NE_{k} |}^{i_{| NE_{k} |},w_{| NE_{k} |}}}.

We should note that the vertices and edges of the tessellation were defined in accordance with the tessellation level. This information will be used to distinguish vertices NV_{k} from V_{k} \ NV_{k}.

We want to determine the types of vertices and edges that generate new polygons in the next stage.

An edge is k-outer (external) if it is an edge of a unique polygon in stage k; if not, it is an inner (internal) edge. When an edge ε := ε_{k,j}^{i_{j},τ_{j}} has τ_{j} = q edges adjacent to its terminal vertex, we state that the edges with τ(ε) as a vertex, are a closed cycle of edges if there are also q polygons in P_{k} with τ(ε) as a vertex. We note that τ_{j} = q does not imply that we have a closed cycle of edges at τ_{j}, because there can be an outer edge among the q edges. If ε_{k,j}^{i_{j},τ_{j}} is an outer edge, then, the reflection ρ_{ε_{k,j}^{i_{j} ,τ_{j}}} closes the cycle of the edges, because q is

the maximum number of polygons in the tiling with a common vertex.

Let v_{k,t}^{j} ∈ V_{k} and A := A(v_{k,t}^{j}) = {ε_{k,1}^{i_{1},τ_{1}}, …, ε_{k,j}^{i_{j},τ_{j}}} be the set of edges of E_{k} that have v_{k,t}^{j} as a vertex, considering the edges numbered anticlockwise. Because we are interested only in vertices that have an external edge in the stage in question (because all polygons having only inner edges have already been counted), we can assume that A has one, and, consequently, at least, two exterior edges. Thus, we assume that the ordinance of the edges of A is applied in such a way that ε_{k,1}^{i_{1},τ_{1}} and ε_{k,j}^{i_{j},τ_{j}}: The first and last edges are k-exterior edges. Such an ordering of A depends only on the choice of the first edge.

Further, two edges with a common vertex are consecutive if the angle between them (at the common vertex) is \frac{2π}{q}. If ε_{k,i}^{i_{i},τ_{i}} and ε_{k,i+1}^{i_{i+1},τ_{i+1}} are consecutive, for all i = 1, 2, …, j − 1, then the set of all edges of v_{k,t}^{j} is called a consecutive set of edges. Otherwise, there is a discontinuity, or a hole, at the edges containing v_{k,t}^{j}.

Given a set of consecutive edges A = {ε_{k,1}^{i_{1},τ_{1}}, ε_{k,2}^{i_{2},τ_{2}}, …, ε_{k,j}^{i_{j},τ_{j}}} of the vertex v_{k,t}^{j}, only the k-exterior edges of A are ε_{k,1}^{i_{1},τ_{1}} and ε_{k,j}^{i_{j},τ_{j}} because the edges ε_{k,2}^{i_{2},τ_{2}}, …, ε_{k,j−1}^{i_{j−1},τ_{j−1}} are the edges of two tiles.

Let α_{1}, ⋯, α_{p} be geodesics supporting the edges of the initial polygon Δ_{0} of the tessellation. The group Γ_{p,q} is generated by the reflections ρ_{α_{1}}, ⋯, ρ_{α_{p}} in the support geodesics of the edges α_{1}, ⋯, α_{p}:

Γ_{p,q} = ⟨ρ_{α_{1}}, ⋯, ρ_{α_{p}}⟩.

A geodesic δ determines two disjoints, connected open half-spaces, H_{δ}^{+} and H_{δ}^{−}, such that δ = \overline{H_{δ}^{+}} ∩ \overline{H_{δ}^{−}}. Hence, a support geodesic can be characterized by two polygons Δ_{1} and Δ_{2} contained in each of these two disjointed half-spaces determined by δ, and satisfying \overline{Δ_{1}} ∩ \overline{Δ_{2}} is an edge contained in δ. In this case, we state that δ supports the polygons Δ_{1}, Δ_{2}, as well as the edge \overline{Δ_{1}} ∩ \overline{Δ_{2}}.

Let δ be a support geodesic of the tessellation (ρ_{δ} ∈ Γ_{p,q}). We state that δ separates the tiles g(Δ_{0}) and h(Δ_{0}) if they belong to different connected components of H^{2}\δ, that is, every continuous path connecting these polygons intercepts δ.

Let ε be an edge of the tessellation with initial vertex v and δ as its support geodesic. We let δ_{i}^{+} denote the geodesic ray with the initial point in v and containing ε, and δ_{i}^{−} as its opposite ray.

Given a support geodesic of the tessellation δ ∈ S and Δ_{i}, Δ_{j} ∈ P_{k}, we consider the following notation:

Δ_{i} |_{δ} Δ_{j} := δ separates the polygons Δ_{i} and Δ_{j},
Δ_{i} ∤_{δ} Δ_{j} := δ does not separate the polygons Δ_{i} and Δ_{j}.

In the following results, we consider an initial polygon Δ_{0} with edges ε_{0,1}^{2,2}, ⋯, ε_{0,p}^{2,2}, and the group Γ_{p,q} = ⟨ρ_{ε_{0,1}^{2,2}}, ⋯, ρ_{ε_{0,p}^{2,2}}⟩ generated by the reflections in these edges.

Proposition 1. Let {p, q} be a tessellation of H^{2}. If q is even, then the k-type of a vertex is always even.

Proof. The proof will be conducted through induction over stage k of the tessellation. Note that the maximum number of edges with a common vertex is q = 2m. For the initial case, the base tile Δ_{0} has vertices v_{0,1}^{2}, ⋯, v_{0,p}^{2}, with 0-type equal to 2.

Now, let us assume that, in stage k, all vertices have even k-type. We prove here that the vertices in stage k + 1 have even (k + 1)-type.

To obtain the tiles in NP_{k+1}, we need to reflect the tiles of NP_{k} in the k-outer edges of the tessellation. Each vertex without a completed cycle has exactly two k-outer edges. In the next stage, each one of these edges will contribute to this vertex with a new adjacent edge (we can have no edges, if the cycle of edges is completed in stage k). Because q is even, the two edges generated by the outer edges in the previous stage cannot be the same.

Thus, through the induction hypothesis, the (k+1)-type of vertices of NV_{k+1} are even.

In the next proposition, we identify the types of new vertices in the tessellation, generated by the reflections in the previous stage.

Proposition 2. Consider a T_{p,q} tessellation and let v_{k}^{i} ∈ V_{k}. If q is even, then v_{k}^{i} ∈ NV_{k} if, and only if, i = 2. If q is odd, then v_{k}^{i} ∈ NV_{k}, if, and, only if, either i = 2 or i = 3, and, when i = 3 there is an edge ε with v = i(ε) and t_{k}(τ(ε)) = q.

Proof. Because the proof in the odd case follows the same steps, we only prove the proposition for q to be even. Given v_{k,l}^{i} ∈ V_{k}, with i = 2, we suppose v_{k,l}^{i} ∉ NV_{k}, that is, v_{k,l}^{i} ∈ NV_{t} for some t < k. Through Proposition 1, the k-type of a vertex is always even; then, the t-type of v_{k,l}^{i} in stage t is at least i = 2, and in stage k, it should have type min{2 + 2(k − t), q} ≥ 2, which is absurd.

Further, let us consider v = v_{k−1,l}^{i} ∈ NV_{k}. We suppose i ≠ 2. Through Proposition 1, i is even, then i ≥ 4, let us enumerate counterclockwise the edges of v_{k−1,l}^{i}. Because it is a set of consecutive edges, we can write ε_{k−1,1}^{i,τ}, ε_{k−1,2}^{i,τ}, …, ε_{k−1,i}^{i,τ}. Only the (k − 1)-outer edges are ε_{k−1,1}^{i,τ} and ε_{k−1,i}^{i,τ}. We label the polygons containing these edges as Δ_{1}, Δ_{2}, …, Δ_{i−1}, with Δ_{j} containing the edges ε_{k−1,j}^{i,τ} and ε_{k−1,j+1}^{i,τ}, for j = 1, …, i.

Thus, Δ_{1} and Δ_{i−1} ∈ NP_{k−1}. To conclude the proof, it is sufficient to show that Δ_{2} (and Δ_{3}, ⋯, Δ_{i−2}) ∈ P_{k−1}. Indeed, if Δ_{2} ∈ P_{r}, then Δ_{2} ∈ NP_{r}, r ≤ k. If ε_{2}, ε_{3} ∈ NP_{r}, then ι(ε_{2}) = ι(ε_{3}) = v ∈ NP_{r}, contradicting the hypothesis of v ∈ NP_{k+1}, because NP_{r} ∩ NP_{r+1} = ∅.

If we suppose that Δ_{2} ∉ P_{k−1}, then Δ_{2} ∈ NP_{k}. Because both Δ_{1}, Δ_{2} ∈ NP_{k}, there are Δ_{1}^{−}, Δ_{2}^{−} ∈ NP_{k−1} such that ρ_{δ_{1}}(Δ_{1}^{−}) = Δ_{1} and ρ_{δ_{2}}(Δ_{2}^{−}) = Δ_{2}, where δ_{i} = Δ_{i} ∩ Δ_{i}^{−} is an edge and ρ_{δ_{i}} is the reflection in the geodesic containing ε_{i}.

Recall that ε_{2} = Δ_{1} ∩ Δ_{2} (because the edges are consecutive). The edge ε_{1} is the first segment of a line connecting the common vertex {v} = ∩_{j=1}^{i}ε_{j} to P_{k−1} along the boundary of Δ_{1}. There is also a line connecting v to P_{k−1}, such that it has ε_{l} as an initial segment. This gives rise to a k-hole, unless ε_{1} = ε_{i}. However, in this case, we changed the parity of vertices v when passing from stage k − 1 to stage k, contradicting Proposition 1. We thus conclude the proof.

We should keep in mind that the given edge ε_{k}^{i,τ} ∈ E_{k}, i(ε_{k}^{i,τ}) and τ(ε_{k}^{i,τ}) denote the initial and final vertices of ε_{k}^{i,τ}, respectively. We can then define the following set:

n_{k}(ε_{k}^{i,τ}) = |{Δ ∈ P_{k} | ι(ε_{k}^{i,τ}) ∈ Δ}|,  (3)

that is, n_{k}(ε_{k}^{i,τ}) is the cardinality of polygons in the tessellation having in common the initial vertex of the edge ε_{k,l}^{i,τ}.

Thus, we can count the new polygons in the following way:

Proposition 3. Let ε = ε_{k}^{2,τ} ∈ NE_{k}. Then, n_{k}(ε) = 1 and n_{k+1}(ε) = 3.

Proof. Let v = ι(ε). Because v has k-type 2, there is another edge ε′ ∈ V_{k}, such that ι(ε′) = v. It follows that ε and ε′ are edges of the same polygon Δ ∈ P_{k}, and hence, n_{k}(ε) = 1. Because both ι(ε) and ι(ε′) have k-type 2, we have ε, ε′ ∈ NE_{k}. Both will give rise to new polygons in the next stage, such that n_{k+1}(ε) = 3. We thus conclude the proof.

If ε_{k}^{2,τ} is a k-outer edge, then it contributes with a new polygon at the level k + 1. If τ < q, then each reflection in the edges with the same vertex will generate different tiles. However, if τ = q, this tile will be counted twice, because there is another k-outer edge that generates the same polygon. It follows that the vertex v = ι(ε_{k}^{2,τ}) will have k + 1-type 4. In the special case in which p = 3, it implies the existence of an edge ε′ ∈ NE_{k+1} of k + 1-type (4, 4). We have just proved the following:

Corollary 4. If ε = ε_{k,l}^{i,τ} ∈ NV_{k}, then (i, τ) = (2, τ), except for the cases τ = q and p = 3, in which (i, τ) = (4, 4) can occur.

3 Recursive counting functions for the growth of the group Γ_{p,q}

We consider the group Γ_{p,q} generated by the reflections on the support geodesics of the edges of the regular polygon Δ_{0} with angles \frac{2π}{q}. We call attention to the fact that reflections in the k-external edges of the polygons at level k are our only instrument to generate the tessellation.

We begin at level 0 with the initial tile Δ_{0}. We obtain level 1 by reflecting Δ_{0} in each of its edges, obtaining p new polygons. All these polygons constitute the new level 1. Given a tile at level 1, let us consider the tiles obtained reflecting this tile at its edges. Level 2 is the set of all tiles obtained similarly at level 1.

At level k, we obtain tiles that are images of Δ_{0} by g ∈ Γ_{p,q} with |g| ≤ k, that is, any tile Δ ∈ P_{k} is in the form g(Δ_{0}) for some g ∈ Γ_{p,q}, such that

|g|_{C} = d_{C}(e, g) ≤ k.

Therefore, we have | B_{k} | = | P_{k} |, where B_{k} is the closed ball with radius k and the center in the identity. In a similar manner, C_{k} = B_{k} \ B_{k−1} is the circumference with radius k and the center in the identity. Thus, | C_{k} | = | NP_{k} |.

3.1 Counting the polygons

We want to find a recursive function for the growth of the group Γ_{p,q}. It is sufficient to determine | NP_{k} | for each k ∈ ℕ, because | P_{k} | = ∑_{i=0}^{k} | NP_{i} |, where | NP_{0} | = | P_{0} | = 1, and we always have | NP_{1} | = p. Let NE_{k}^{i,j} be the set of edges of k-type (i, j) in the set NE_{k}, and let NV_{k}^{i} denote the set of vertices of k-type i in NV_{k}. From propositions 1 and 2, we have the following cases:

i) p > 3 and q = 2m.

Only external edges (at level k − 1) contribute towards new polygons at level k. Moreover, an edge ε ∈ E_{k−1} is an external edge if, and only if, its (k − 1)-type is (2, j). Let us assume that q = 2m is even; then, the possible types for an external edge are (2, 2), (2, 4), …, (2, q − 2), (2, q). Each external edge of type (2, 2i), i ≤ m − 1 gives rise to a new polygon at the next level. Because q = 2m, for any edge ε ∈ NE_{k−1}^{2,q}, there is another edge ε′ ∈ NE_{k−1}^{2,q} with a common vertex τ(ε) = τ(ε′), and thus the reflection in ε and ε′ gives rise to the same polygon. In other words,

| NP_{k} | = ∑_{i=1}^{m−1} | NE_{k−1}^{2,2i} | + \frac{1}{2}| NE_{k−1}^{2,q} | .  (4)

ii) p = 3 and q = 2m.

In addition to the considerations of i), in this case, we also have external edges of type (4, 4), each of which will contribute with one more polygon at the next level. Then,

| NP_{k} | = ∑_{i=1}^{m−1} | NE_{k−1}^{2,2i} | + \frac{1}{2}| NE_{k−1}^{2,q} | + | NE_{k−1}^{4,4} | .  (5)

iii) p > 3 and q = 2m + 1 > 3.

For any edge ε ∈ E_{k−1}^{2,j}, with j < q − 1, the reasoning is the same as with the even case. If ε ∈ NE_{k−1}^{2,q−1}, there are edges ε′ and ε′′ ∈ NE_{k−1}^{2,q} that have a common vertex τ(ε) = τ(ε′) = τ(ε′′), and thus the reflection in ε′ and ε′′ gives rise to two new polygons that have ε as a common edge. Finally, for any edge ε ∈ NE_{k−1}^{2,q} there is another edge ε′ ∈ NE_{k−1}^{2,q} with a common vertex τ(ε) = τ(ε′), and thus, the reflections in ε and ε′ give rise to only one new polygon. It follows that

| NP_{k} | = ∑_{i=2}^{q−1} | NE_{k−1}^{2,i} | + \frac{1}{2}| NE_{k−1}^{2,q} | .  (6)

iv) p = 3 and q = 2m + 1.

If we do not have edges of type (2, 2), edges of types (3, 4) and (4, 4) will appear. Thus,

| NP_{k} | = ∑_{i=4}^{q−1} | NE_{k−1}^{2,i} | + | NE_{k−1}^{3,4} | + | NE_{k−1}^{4,4} | + \frac{1}{2}| NE_{k−1}^{2,q} | .  (7)

v) p ≥ 6 and q = 3.

We will have only edges of types (2, 2) and (2, 3). Each edge of type (2, 2) will contribute with one new polygon; for ε ∈ NE_{k}^{2,3}, there is ε′ ∈ NE_{k}^{2,3}, such that ε and ε′ have a common vertex v, and the angle between them in v is 2π/3. Thus, the pair ε, ε′ will give an origin only to one new polygon. The total is

| NP_{k} | = | NE_{k−1}^{2,2} | + \frac{1}{2}| NE_{k−1}^{2,3} | .  (8)

We will then need to define recursive functions for | NE_{k}^{2,i} |, | NE_{k}^{3,4} |, and | NE_{k}^{4,4} | to define a recursive function to | NP_{k} |,.

3.2 Counting the vertices

We have determined the formulae for | P_{k} | and now seek to determine the formulae for | V_{k} |. We have | V_{k} | = | NV_{k} | + | V_{k−1} |. For k = 0, | V_{0} | = | NV_{0}^{2} | = p and | NV_{0}^{l} | = 0 for l > 2.

i) We suppose p > 3 and q = 2m, m ≥ 2.

For k = 1,

| NV_{1}^{2} | = p(p − 2),
| NV_{1}^{4} | = p,
| NV_{1} | = p(p − 2) + p = | NV_{1}^{2} | + | V_{0} |.

(9)

In a general way, if ε ∈ NE_{k−1}^{2,j} with j ≤ q−1, then the reflection in ε will be a new polygon Δ ∈ NP_{k}, giving origin to p − 3 new edges of type (2, 2) in NE_{k}, providing p − 3 + 1 = p − 2 new vertices of type 2, totaling (p − 2) ∑_{j=2}^{q−1} | NE_{k−1}^{2,j} | vertices of type 2.

However, if ε_{1} ∈ NE_{k−1}^{2,q}, there exists ε_{2} ∈ NE_{k−1}^{2,q}, with a common vertex with ε_{1}, such that τ_{ε_{1}}(Δ) = τ_{ε_{2}}(Δ). We have p − 4 new edges of type (2, 2), and p − 4 + 1 = p − 3 new vertices of type 2 in NV_{k}. Therefore, the total in NV_{k} is

| NV_{k}^{2} | = (p − 2) ∑_{j=2}^{q−1} | NE_{k−1}^{2,j} | + (p − 3)\frac{| NE_{k−1}^{2,q} |}{2} .  (10)

Now, if | V_{k−1} | is known, then

| V_{k} | = | NV_{k}^{2} | + | V_{k−1} | .  (11)

ii) q = 2m + 1, m ≥ 2 and p > 3.

When k = 0, we have | NV_{0}^{2} | = p and | NV_{0}^{l} | = 0 for l > 2. For k = 1, we have the same result of (9).

Now, if ε ∈ NV_{k−1}^{2,j} with 3 < j < q − 1, the reflection in ε is a new polygon Δ in NP_{k}, giving origin to p − 3 new edges of type (2, 2) in NE_{k}^{2,2}; then, p − 3 + 1 = p − 2 new vertices of type 2 are originated, totaling (p − 2) ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | vertices of type 2.

However, if ε ∈ NE_{k−1}^{2,q−1}, there exists ε′ ∈ NE_{k−1}^{2,q−1} such that the reflections in ε and ε′ give origin to distinct polygons, but with a common edge ε_{1} ∈ NE_{k−1}^{3,q}. Thus, ε gives origin to p − 4 new edges of type (2, 2), and soon p − 4 + 1 = p − 3 new vertices of type 2 in NV_{k}, with a total of (p − 4)| NE_{k−1}^{2,q−1} |.

Because ε originates ε_{1} ∈ NE_{k}^{2,3}, we have a1/2 vertex of type 3, totaling 1/2| NE_{k−1}^{2,q−1} | vertices of type 3.

If ε ∈ NE_{k−1}^{2,q}, there exists ε_{1} ∈ NE_{k−1}^{2,q} with a common vertex with ε, such that τ_{ε}(Δ) = τ_{ε_{1}}(Δ). We have p − 4 new edges of type (2, 2), giving p − 4 + 1 = p − 3 new vertices of type 2 in NV_{k}, for a total of (p − 4)| NE_{k−1}^{2,q} |/2. Put together, we have

| NV_{k}^{2} | = (p − 2) ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | + (p − 4)| NE_{k−1}^{2,q−1} | + (p − 4)\frac{| NE_{k−1}^{2,q} |}{2},

| NV_{k}^{3} | = \frac{| NE_{k−1}^{2,q−1} |}{2}.

(12)

The total of level k is given by

| V_{k} | = | NV_{k}^{2} | + | NV_{k}^{3} | + | V_{k−1} | .  (13)

iii) p = 3 and q = 2m.

As in the case of polygons, the edges of type (2, q) at level k − 1 will not contribute to the new vertices at the next level k. Edges of type (4, 4) will contribute with one additional vertex. All new vertices are of type 2. Thus,

| NV_{k}^{2} | = ∑_{j=4}^{q−2} | NE_{k−1}^{2,j} | + | NE_{k−1}^{4,4} | .  (14)

Equation (11) provides the total.

iv) p = 3 and q = 2m + 1.

The edges of type (2, j) with 4 ≤ q − 2 at level k − 1 will contribute with new vertices of type 2 at the next level k, and similarly for the edges of type (4, 4). In this case, we also have edges of type (3, 4). Thus,

| NV_{k}^{2} | = ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | + | NE_{k−1}^{3,4} | + | NE_{k−1}^{4,4} |,

| NV_{k}^{3} | = \frac{| NE_{k−1}^{2,q−1} |}{2} ,

(15)

where Equation (13) gives the total.

v) p ≥ 6 and q = 3.

For k = 1, we have

| NV_{1}^{2} | = p(p − 4), | NV_{1}^{3} | = p, | NV_{1} | = p(p − 4) + p = | NV_{1}^{2} | + | V_{0} |..  (16)

For k ≥ 2, we have only new edges of types (2, 2) and (2, 3). If ε ∈ NE_{k−1}^{2,3}, then there exists ε′ ∈ NE_{k−1}^{2,3}, such that τ_{ε}(Δ) = τ_{ε′}(Δ). Thus, ε gives origin to \frac{1}{2}(p − 6) new edges of type (2, 2) in NE_{k}^{2,2}, for a total of 2\frac{1}{2}(p−6) vertices in NV_{k}^{2}. We will then have (p−6)| NE_{k−1}^{2,3} | vertices in NV_{k}^{2}.

Further, ε will give origin to p − 4 + 1 edges in NE_{k}^{2,3}, similarly to ε′, giving \frac{1}{2}(p − 5) new edges in NE_{k}^{2,3}. We will thus have \frac{1}{2}(p−5) new vertices in NV_{k}^{3}, for a total of \frac{1}{2}(p−5)| NE_{k}^{2,3} | vertices.

If ε ∈ NE_{k−1}^{2,2}, then the reflection in ε will give origin to a new polygon at level k. We will have p − 5 new edges of type (2, 2), and p − 5 + 1 = p − 4 new vertices of type 2, for a total of (p − 4)| NE_{k−1}^{2,2} | vertices of type 2.

Each polygon in NP_{k−1} has p − 5 consecutive edges of type (2, 2), ε_{1}, …, ε_{p−5}, for a total of p − 5 + 1 = p − 4 consecutive vertices. They will give origin to p − 4 − 2 = p − 6 new vertices of type 3 at level k, totaling (p − 6)| NP_{k−1} | vertices of type 3. Therefore,

| NV_{k}^{2} | = (p − 6)| NE_{k−1}^{2,3} | + (p − 4)| NE_{k−1}^{2,2} |,

| NV_{k}^{3} | = \frac{p − 5}{2}| NE_{k−1}^{2,3} | + (p − 6)| NP_{k} |.

(17)

Equation (13) provides the total amount.

3.3 Counting the edges

Subsections 3.1 and 3.2 provide recursive formulae for | NP_{k} | and | NV_{k} |, depending only on | NE_{k}^{j,l} |. Thus, recursive formulae for | NE_{k}^{j,l} | are required.

First, the k-type (i, j) of an edge is strictly increased (with k) for both i and j until both reach the maximum value q. We are interested in the edges in NE_{k}. How do new edges arise?

We will consider the possible cases for the edges in {p, q}. Namely, the recursive formulae that express the number of edges at each level k demand a study of five different cases with regard to the parity of p and q.

i) p ≥ 4 and q = 2m.

Let ε ∈ NP_{k−1} be an external edge of (k − 1)-type (2, j). We will assume that j ≤ q − 2. The edge ε is an edge of an external polygon Δ, and, because j ≤ q −2, the reflected polygon Δ′ = ρ_{ε}(Δ) will have all but ε as an external edge. That is, each ε ∈ ∪_{j=1}^{q−2} NE_{k−1}^{2,j} will give rise to (p − 1) distinct edges in NE_{k}.

Because all types of edges are always even, j = q. Given an edge ε_{1} ∈ NE_{k−1}^{2,q}, there is another edge ε_{2} ∈ NE_{k−1}^{2,q}, ε_{1} ≠ ε_{2}, such that τ(ε_{1}) = τ(ε_{2}) = v. For i = 1, 2, let Δ_{i} ∈ P_{k−1} be such that ε_{i} is an external edge of Δ_{i}, and let ε_{i}^{∗} be another edge of Δ_{i} having v as a vertex. Because j = q, ε_{2} ∈ ρ_{ε_{1}}(Δ_{1}) and ε_{1} ∈ ρ_{ε_{2}}(Δ_{2}), and actually ρ_{ε_{1}}(ε_{1}^{∗}) = ε_{2} and ρ_{ε_{2}}(ε_{2}^{∗}) = ε_{1}, it follows that ρ_{ε_{1}}(Δ_{1}) = ρ_{ε_{2}}(Δ_{2}). This is a new polygon having p edges, except for ε_{1} and ε_{2}, as external edges at level k. In short, for the case of q = 2m,

| NE_{k} | = (p − 1) ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | + \frac{(p − 2)}{2}| NE_{k−1}^{2,q} |

= (p − 1) ∑_{j=1}^{m−1} | NE_{k−1}^{2,2j} | + \frac{(p − 2)}{2}| NE_{k−1}^{2,q} | .  (18)

The formulae for | NE_{k} | depend on the terms of level k − 1. We must then study these terms to obtain the recursive formulae. We call attention to the fact that the formulae can be implemented in an algebraic computer system.

Let ϵ ∈ E_{k−1} be a vertex of (k − 1)-type (2, j). Because ε ∈ NE_{k−1}, it is the edge of a new polygon at this level (k − 1). Because new polygons are generated based on a reflection of existing polygons in an external edge of the previous level (k − 2), we must look at the external edges of this level, that is, the edges of (k − 2)-type (2, j), with 2 ≤ j ≤ q.

If ϵ ∈ NE_{k−2}^{2,2}, it is the edge of a polygon Δ ∈ P_{k−2}; considering the reflection ρ_{ε} in the geodesic containing ε, ρ_{ε}(Δ) is a polygon containing 1 edge in E_{k−1}^{4,4} (actually this is the edge ε itself), 2 edges in NE_{k−1}^{2,4} (those adjacent to ε), and all the other (p − 3) edges will be in NE_{k−1}^{2,2}. Therefore, each ε ∈ NE_{k−2}^{2,2} will generate

2 edges ∈ NE_{k−1}^{2,4},
p − 3 edges ∈ NE_{k−1}^{2,2},
1 edge = ε ∈ E_{k−1}^{4,4} .

(19)

Now consider ε ∈ NE_{k−2}^{2,j}, with 4 ≤ j < q. Because q is even, we have j < q − 1. Similar to the previous case, ε is an edge of a polygon Δ ∈ P_{k−2}; considering the reflection ρ_{ε} in the geodesic containing ε, ρ_{ε}(Δ) is a polygon containing 1 edge in E_{k−1}^{4,j+2} (actually, this is the edge ε itself). The edges of ρ_{ε}(Δ) adjacent to ε at its initial (type 2) and final (type j) vertices will be the edges of NE_{k−1}^{2,4} and NE_{k−1}^{2,j+2}, respectively. All remaining (p − 3) edges of ρ_{ε}(Δ) with no intersection with ε will be vertices in NE_{k−1}^{2,2}. In short, each ε ∈ E_{k−2}^{2,j} generates

1 edge = ε ∈ E_{k−1}^{4,j+2},
1 edge ∈ NE_{k−1}^{2,4},
p − 3 edges ∈ NE_{k−1}^{2,2},
1 edge ∈ NE_{k−1}^{2,j+2} .

(20)

The case j = q can occur only for an even q. In this case, there are two edges ε and ε′ of (k − 2) type (2, q) joining a common vertex v of type q. These are edges of distinct polygons Δ, Δ′ ∈ P_{k−2}; however, ρ_{ε}(Δ) = ρ_{ε′}(Δ′). We can see that ε and ε′ become edges of type (4, q), the other two distinct edges adjacent to ε and ε′ become edges of (k − 1)-type (2, 4), and the other (p − 4) edges of ρ_{ε}(Δ) = ρ_{ε′}(Δ′) are edges of type (2, 2). In short, each ε ∈ NE_{k−2}^{2,q} generates

\frac{1}{2} edge = ε ∈ E_{k−1}^{4,q},

1 edges ∈ NE_{k−1}^{2,4},

\frac{p − 4}{2} edges ∈ NE_{k−1}^{2,2} .

(21)

Now, we can put together the above results to obtain the number of edges. The following function is useful for controlling the appearance of the types of edges when k increases. This function will be used throughout the rest of the present paper. Let

f_{l}(j) = \begin{cases}1, & if j ≤ l − 1; \\ 0 , & if j > l − 1 , \end{cases}  (22)

for l, j ∈ ℤ and l ≥ 1. Then, we have the following:

Theorem 5. Let {p, q} be a tessellation with p ≥ 4, q = 2m, m ≥ 2, and k ≥ 2, all of which are integers. Then, for the two initial levels, | NE_{0}^{2,2} | = | E_{0} | = p; | NE_{0}^{i,j} | = 0 for (i, j) ≠ (2, 2); | NE_{1}^{2,2} | = (p − 3)p; and | NE_{1}^{2,4} | = 2p; | NE_{1}^{2,j} | = 0 for j > 4. For the other levels,

| NE_{k−1}^{2,2} | = (p − 3)| NE_{k−2}^{2,2} | + (p − 3)f_{m}(2) ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} | + (p − 4)\frac{| NE_{k−m}^{2,4} |}{2}  (23)

| NE_{k−1}^{2,4} | = 2| NE_{k−2}^{2,2} | + ∑_{j=2}^{m} | NE_{k−j}^{2,4} |  (24)
| NE_{k−j}^{2,4} | = 0 for k ≤ j
| NE_{k−1}^{2,2j} | = | NE_{k−(j−1)}^{2,4} |, for 2 < j ≤ m .  (25)

The total at level k is

| NE_{k} | = (p − 1)(p − 3 + 2f_{m}(2))| NE_{k−2}^{2,2} | + (p − 1)(f_{m}(2)(p − 2) + f_{m}(3)) ∑_{j=2}^{m−2} | NE_{k−j}^{2,4} |

+ ((p − 1)(p − 2)f_{m}(2) + \frac{p − 2}{2})| NE_{k−(m−1)}^{2,4} | + (p − 1)(\frac{(p − 4)}{2} + f_{m}(2))| NE_{k−m}^{2,4} | .

Proof. Applying together the edges of the same type in (19), (20) and (21), and because q = 2m, it follows that

| NE_{k−1}^{2,2} | = (p − 3) ∑_{j=2}^{q−2} | NE_{k−2}^{2,j} | + (p − 4)\frac{| NE_{k−2}^{2,q} |}{2} = (p − 3) ∑_{j=1}^{m−1} | NE_{k−2}^{2,2j} |

+ (p − 4)\frac{| NE_{k−2}^{2,2m} |}{2}  (26)
| NE_{k−1}^{2,4} | = 2| NE_{k−2}^{2,2} | + ∑_{j=4}^{q−2} | NE_{k−2}^{2,j} | + 2\frac{| NE_{k−2}^{2,q} |}{2} = 2| NE_{k−2}^{2,2} | + ∑_{j=2}^{m} | NE_{k−2}^{2,2j} |  (27)
| NE_{k−1}^{2,j+2} | = | NE_{k−2}^{2,j} |, for 4 ≤ j ≤ q − 2  (28)

The relation (28) is fundamental, and we obtain

| NE_{k−2}^{2,2j} | = | NE_{k−j}^{2,4} | ,  (29)

for 2 ≤ j ≤ m. Applying (29) in (26) and (27), we have

| NE_{k−1}^{2,2} | = (p − 3)| NE_{k−2}^{2,2} | + (p − 3) ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} | + (p − 4)\frac{| NE_{k−m}^{2,4} |}{2}  (30)

| NE_{k−1}^{2,4} | = 2| NE_{k−2}^{2,2} | + ∑_{j=2}^{m} | NE_{k−j}^{2,4} |  (31)
| NE_{k−1}^{2,2j} | = | NE_{k−(j−1)}^{2,4} |, for 2 < j ≤ m ,  (32)

where | NE_{k−j}^{2,4} | = 0 for k ≤ j. The expression for | NE_{k−1}^{2,2} | in (23) follows from (31), where the function f_{l}(j) is used to obtain the general case for any k in the sum. To prove the formula for | NE_{k} |, from (18)

| NE_{k} | = (p − 1) ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | + \frac{(p − 2)}{2}| NE_{k−1}^{2,q} | = (p − 1) ∑_{j=1}^{m−1} | NE_{k−1}^{2,2j} | + \frac{(p − 2)}{2}| NE_{k−1}^{2,2m} |

Now, using relations (30)−(32), and considering the relation ∑_{j=3}^{m−1} | NE_{k−(j−1)}^{2,4} | = ∑_{j=2}^{m−2} | NE_{k−j}^{2,4} |, the result follows .

ii) p ≥ 4 and q = 2m + 1.

In this case, we must be more careful. If j = q − 1, given an edge ε_{1} ∈ NE_{k−1}^{2,q−1}, there is another edge ε_{2} ∈ NE_{k−1}^{2,q−1} joining a common vertex. Because (for i = 1, 2) Δ_{i} is a polygon in P_{k−1}, such that ε_{i} is an (exterior) edge of Δ_{i}, we have ε = ρ_{ε_{1}}(Δ_{1}) ∩ ρ_{ε_{2}}(Δ_{2}), and thus each of the edges ε_{1} and ε_{2} contribute with (p − 2) new external edges at level k, in addition to ε. Now, ε is also a new edge in | NE_{k} | and must also be computed. Because ε_{1} and ε_{2} give origin to the same edge, each one contributes with \frac{1}{2} an edge. Finally, if j = q, we have a similar reasoning as in case (i). Then, in short, for q = 2m + 1,

| NE_{k} | = (p − 1) ∑_{j=2}^{q−2} | NE_{k−1}^{2,j} | + (p − \frac{3}{2})| NE_{k−1}^{2,q−1} | + \frac{(p − 2)}{2}| NE_{k−1}^{2,q} | .  (33)

Now, let ε ∈ NE_{k−2}^{2,j}. The case j = q can occur only for an even q, and thus 2 ≤ j ≤ q −1. For j < q − 1, we have the same reasoning as case i), obtaining (19) and (20).

For j = q − 1, let ε = ε_{1}, ε_{2}, …, ε_{q−1} be the set of all q − 1 edges with the common vertex v = τ(ε) ∈ V_{k−2} numbered such that the angle between the consecutive edges is 2π/q. Because q − 1 = 2m, ε_{q−1} ∈ NE_{k−2}^{2,q−1}. Let Δ ∈ P_{k−2} be the polygon containing ε; then, Δ_{1} = ρ_{ε}(Δ) and Δ_{2} = ρ_{ε_{q−1}}(⋯ (ρ_{ε_{2}}(Δ)) ⋯) have a common edge ε′ of type (3, q). The other distinct edge of Δ_{1} adjacent to ε′ is an edge of (k − 1)-type (3, q). The other (p − 4) edges of Δ_{1} are edges of type (2, 2). In short, ε ∈ NE_{k−2}^{2,q−1} generates

1 edge = ε ∈ E_{k−1}^{4,q},

\frac{1}{2} edges ∈ NE_{k−1}^{3,q},

1 edges ∈ NE_{k−1}^{2,4},

1 edge ∈ NE_{k−1}^{2,3},

p − 4 edges ∈ NE_{k−1}^{2,2} .

(34)

Now, we obtain the following result.

Theorem 6. Let {p, q} be a tessellation with p ≥ 4, q = 2m + 1, m ≥ 2 and k ≥ 2, all of which are integers. Then, for the two initial levels, we have | NE_{0}^{2,2} | = | E_{0} | = p, | NE_{0}^{i,j} | = 0 for (i, j) ≠ (2, 2), | NE_{1}^{2,2} | = (p − 3)p; | NE_{1}^{2,4} | = 2p, and | NE_{1}^{2,j} | = 0 for j > 4; and for the other levels

| NE_{k−1}^{2,2} | = (p − 3)| NE_{k−2}^{2,2} | + (p − 3)f_{m}(2) ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} | + (p − 3) ∑_{j=1}^{m−1} | NE_{k−(j+m)}^{2,4} |+(35)

+ (p − 4)| NE_{k−m}^{2,4} |
| NE_{k−1}^{2,4} | = 2| NE_{k−2}^{2,2} | + ∑_{j=1}^{m−1} | NE_{k−(j+m)}^{2,4} | + ∑_{j=2}^{m} | NE_{k−j}^{2,4} |  (36)
| NE_{k−1}^{2,2j} | = | NE_{k−(j−1)}^{2,4} |, for 2 ≤ j ≤ m  (37)
| NE_{k−1}^{2,2j+1} | = | NE_{k−(j+m−1)}^{2,4} |, for 1 ≤ j ≤ m  (38)
| NE_{k−1}^{2,3} | = | NE_{k−m}^{2,4} |  (39)
| NE_{k−1}^{3,q} | = \frac{| NE_{k−m}^{2,4} |}{2} ,  (40)

The total at level k is

| NE_{k} | = (p − 1)(p − 3 + 2f_{m}(2))| NE_{k−2}^{2,2} | + (p − 1)^{2}f_{m}(3) ∑_{j=3}^{m−1} | NE_{k−(j−1)}^{2,4} |

+ ((p − 1)(p − 2)f_{m}(2) + (p − 3/2))| NE_{k−(m−1)}^{2,4} | + (p − 1)^{2}f_{m}(2) ∑_{j=2}^{m−1} | NE_{k−(j+m−1)}^{2,4} |

+ (p^{2} − 7p/2 + 2 + f_{m}(2)(p − 1))| NE_{k−(2m−1)}^{2,4} | + (p − 1)(p − 3 + f_{m}(2))| NE_{k−m}^{2,4} | .

Proof. Applying together the edges of the same type in (19), (20), (34), and since because q − 1 = 2m, it follows that

| NE_{k−1}^{2,2} | = (p − 3) ∑_{j=2}^{q−2} | NE_{k−2}^{2,j} | + (p − 4)| NE_{k−2}^{2,q−1} |  (41)

| NE_{k−1}^{2,4} | = 2| NE_{k−2}^{2,2} | + ∑_{j=3}^{q−1} | NE_{k−2}^{2,j} |  (42)
| NE_{k−1}^{2,j+2} | = | NE_{k−2}^{2,j} |, for 3 ≤ j ≤ q − 2  (43)
| NE_{k−1}^{2,3} | = | NE_{k−2}^{2,q−1} |  (44)
| NE_{k−1}^{3,q} | = \frac{| NE_{k−2}^{2,q−1} |}{2} ,  (45)

and | NE_{k−1}^{2,3} | = | NE_{k−1}^{3,q} | = 0 for k ≤ \frac{q−3}{2}.

In the equations (41) and (42), the term | NE_{k−2}^{2,j} | appears with even and odd j. When (43) is used

| NE_{k−2}^{2,2j+1} | = | NE_{k−(j+1)}^{2,3} |, for 1 ≤ j ≤ m  (46)

and

| NE_{k−2}^{2,2j} | = | NE_{k−j}^{2,4} |, for 2 ≤ j ≤ m .  (47)

Because q − 1 = 2m, from (44) and (45),

| NE_{k−1}^{2,3} | = | NE_{k−m}^{2,4} | .  (48)

Now, from (46), we obtain | NE_{k−(j+1)}^{2,3} | = | NE_{k−(j+m)}^{2,4} |, and applying together (47),

| NE_{k−2}^{2,2j+1} | = | NE_{k−(j+m)}^{2,4} |, for 1 ≤ j ≤ m .  (49)

Similarly, from (45) and (46),

| NE_{k−1}^{3,q} | = \frac{| NE_{k−m}^{2,4} |}{2} .  (50)

The expression for | NE_{k−1}^{2,2} | follows from (41), where the function f_{l}(j) is employed to obtain the general case for any k in the sum. The formula for | NE_{k} | is obtained by applying together the relations (36) − (40) in (33), and through the same reasoning of Theorem 5, the result follows .

iii) p ≥ 6 and q = 3.

In this case, there are no holes between the new edges from one level to the next. Thus, all vertices at the k − 1 level become vertices of type 3 at level k. We do not need information on level k − 2. Given ε ∈ NE_{k−1}^{2,3}, ε is an edge of a polygon Δ ∈ P_{k−1}; there is another edge ε′ ∈ NE_{k−1}^{2,3} in another polygon Δ′ ∈ P_{k−1} with the same final vertex v of ε. Considering the reflections ρ_{ε} and ρ_{ε′} on the geodesics containing ε and ε′, respectively, then ρ_{ε}(Δ) = ρ_{ε′}(Δ′) = Δ′′.

Considering the polygon Δ, because ε ∈ E_{k−1}^{2,3} and p ≥ 6, there is a sequence of adjacent edges ε = ε_{1}, ε_{2}, ⋯, ε_{p−3} such that ε_{p−3} ∈ E_{k−1}^{2,3} and ε_{2}, ⋯, ε_{p−4} ∈ E_{k−1}^{2,2}. Thus, we have (p − 5) edges of E_{k−2}^{2,2} which contains (p − 4) vertices, where each one will give origin to a new edge of E_{k}^{3,3}. We will have the same edges if we begin from ε_{p−3}, where (p − 4)/2 new edges of E_{k}^{3,3} will be generated. We also have one more new edge of E_{k}^{2,3} adjacent to these adjacent edges above. All remaining (p − 6) edges of ρ_{ε}(Δ) will be vertices in E_{k}^{2,2}. In short, each ε ∈ E_{k−1}^{2,3} generates

\frac{p − 4}{2} edges ∈ E_{k}^{3,3},

1 edge ∈ E_{k}^{2,3},

\frac{p − 6}{2} edges ∈ E_{k}^{2,2} .

(51)

If ε ∈ NE_{k−1}^{2,2}, ε is an edge of a polygon Δ_{1} ∈ P_{k−1}. Let Δ′_{1} be its reflection in the geodesic containing ε, ρ_{ε}(Δ_{1}) = Δ′_{1}; Δ′_{1} then is a polygon containing 1 edge in E_{k}^{3,3} (actually this is the edge ε itself). The edges of Δ′_{1}, which are adjacent to ε, will be edges of E_{k}^{3,3}, and were counted above. We have two more new edges of NE_{k}^{2,3} adjacent to these adjacent edges above. All remaining (p − 5) edges of ρ_{ε}(Δ_{1}) will be vertices in NE_{k}^{2,2}. In short, each ε ∈ NE_{k−1}^{2,2} generates

2 edges ∈ NE_{k}^{2,3},

p − 5 edges ∈ NE_{k}^{2,2} . (52)

Thus, putting together the edges of the same type in (51) and (52), it follows that

Theorem 7. Let {p, 3} be a tessellation with p ≥ 6 and k ≥ 2, all of which are integers. Then, for the two initial levels, we have| NE_{0}^{2,2} | = | E_{0} | = p, | NE_{0}^{i,j} | = 0 for (i, j) ≠ (2, 2), | NE_{1}^{2,2} | = p(p − 5), | E_{1}^{2,3} | = 2p and | NE_{1}^{3,3} | = p, and for the other levels,

| NE_{k}^{2,2} | = (p − 5)| NE_{k−1}^{2,2} | + \frac{p − 6}{2}| NE_{k−1}^{2,3} |  (53)
| NE_{k}^{2,3} | = 2| NE_{k−1}^{2,2} | + | NE_{k−1}^{2,3} |  (54)
| NE_{k}^{3,3} | = \frac{p − 4}{2}| NE_{k−1}^{2,3} | ,  (55)

The total at level k is

| NE_{k} | = (p − 3)| NE_{k−1}^{2,2} | + (p − 4)| NE_{k−1}^{2,3} | .

Now, we turn to case p = 3. Then, q ≥ 6, and there are no edges of type (2, 2) at levels k > 1. Let ϵ ∈ E_{k−1} be an edge of (k − 1)-type (2, j). Thus, ε ∈ NE_{k−1} because it is an edge of a new polygon at this level (k − 1). Because new polygons are generated through reflections of the existing polygons at an external edge of the previous level (k − 2), we must look at the external edges of such level, that is, the edges of (k − 2)-type (2, j), with 2 < j ≤ q.

iv) p = 3, q = 2m ≥ 6.

Consider ε ∈ NE_{k−2}^{2,j}, with 4 ≤ j < q. Because q is even, we have j < q − 1. Now, ε is an edge of a triangle Δ ∈ NP_{k−2}, and considering the reflection ρ_{ε} in the geodesic containing ε, ρ_{ε}(Δ) is a triangle containing one edge in E_{k−1}^{4,j+2} (actually this is the edge ε itself). The two edges of ρ_{ε}(Δ) adjacent to ε at its initial (type 2) and final (type j) vertex will be edges of NE_{k−1}^{2,4} and NE_{k−1}^{2,j+2}, respectively. In short, each ε ∈ NE_{k−2}^{2,j} generates

1 edge = ε ∈ E_{k−1}^{4,j+2},
1 edge ∈ NE_{k−1}^{2,4},
1 edge ∈ NE_{k−1}^{2,j+2} .

(56)

For j = q, there are two edges ε and ε′ of (k − 2) type (2, q) joining a common vertex v of type q. These are edges of distinct polygons Δ, Δ′ ∈ P_{k−2}; however, ρ_{ε}(Δ) = ρ_{ε′}(Δ′), and we can see that ε and ε′ become edges of type (4, q). The triangle ρ_{ε}(Δ) will originate only one new edge, which is the same new edge as ρ_{ε′}(Δ). In short, each pair ε, ε′ ∈ NE_{k−2}^{2,q} generates

1 edge = ε ∈ E_{k−1}^{4,q},
1 edge = ε′ ∈ NE_{k−1}^{4,q},
1 edge ∈ NE_{k−1}^{4,4} .

(57)

Now, if ε ∈ NE_{k−2}^{4,4}, there exists Δ ∈ P_{k−2} with ε ∈ Δ such that ρ_{ε}(Δ) will originate two new edges of E_{k−1}^{2,6}.

Thus, we can prove the following result.

Theorem 8. Let {p, q} be a tessellation with p = 3, q = 2m, m ≥ 2 and k ≥ 2, all of which are integers. Then, for the two initial levels, we have| NE_{0}^{2,2} | = | E_{0} | = 3; | NE_{0}^{i,j} | = 0 for (i, j) ≠ (2, 2), | NE_{1}^{2,4} | = 2p; | NE_{1}^{2,j} | = 0 for j ≠ 4, and for the other levels

| NE_{k−1}^{2,4} | = ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} |  (58)
| NE_{k−1}^{2,2(j+1)} | = | NE_{k−j}^{2,4} |, for 2 ≤ j ≤ m − 1  (59)
| NE_{k−1}^{4,4} | = \frac{1}{2}| NE_{k−2}^{2,q} |  (60)
| NE_{k−1}^{2,6} | = 2| NE_{k−2}^{4,4} | ,  (61)

The total at level k is

| NE_{k} | = 2(f_{m−1}(2) + f_{m}(3)) ∑_{j=2}^{m−2} | NE_{k−j}^{2,4} | + \frac{5}{2}| NE_{k−m+1}^{2,4} | + | NE_{k−m}^{2,4} | .

Proof. Putting together the edges of the same type from (56) and (57), and because q − 2 = 2m − 2 = 2(m − 1), it follows that

| NE_{k−1}^{2,4} | = ∑_{j=4}^{q−2} | NE_{k−2}^{2,j} | = ∑_{j=2}^{m−1} | NE_{k−2}^{2,2j} |  (62)
| NE_{k−1}^{2,j+2} | = | NE_{k−2}^{2,j} |, for 4 ≤ j ≤ q − 2  (63)
| NE_{k−1}^{4,4} | = \frac{1}{2}| NE_{k−2}^{2,q} |  (64)
| NE_{k−1}^{2,6} | = 2| NE_{k−2}^{4,4} |  (65)

where | NE_{k−j}^{2,4} | = 0 for k ≤ j. The relation (63) is fundamental, and we obtain that

| NE_{k−2}^{2,2j} | = | NE_{k−j}^{2,4} | ,

for 2 ≤ j ≤ m − 1. Applying this relation in (62) and (63), we have

| NE_{k−1}^{2,4} | = ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} |  (66)
| NE_{k−1}^{2,2(j+1)} | = | NE_{k−j}^{2,4} |, for 2 ≤ j ≤ m − 1 .  (67)

We need a general formula for | NE_{k} |, for p = 3. Let ε ∈ NP_{k−1} be an external edge of (k − 1)-type (2, j). We assume that j ≤ q − 2. The edge ε is an edge of an external polygon Δ, and, because j ≤ q −2, the reflected polygon Δ′ = ρ_{ε}(Δ) will have all but ε as an external edge. That is, each ε ∈ ∪_{j=1}^{q−2} NE_{k−1}^{2,j} will give rise to 2 new distinct edges in NE_{k}. Given an edge ε_{1} ∈ NE_{k−1}^{2,q}, by (64), ε_{1} will give origin to 1/2 of a new edge of NE_{k}^{4,4}. Finally, given ε_{2} ∈ NE_{k−1}^{4,4}, by (65), two new edges of NE_{k}^{2,6} will be originate . Therefore, we have

| NE_{k} | = 2 ∑_{j=2}^{m−1} | NE_{k}^{2,2j} | + \frac{1}{2}| NE_{k−1}^{2,2m} | + 2| NE_{k}^{4,4} | .  (68)

Now, using (68) and the relations (64) − (67), the result follows .

v) p = 3, q = 2m + 1 ≥ 7.

Supposing for the moment that 4 ≤ j ≤ q − 2, then q > 4, and each ε ∈ NE_{k−2}^{2,j} generates the same result as (56).

For j = q − 1, let ε = ε_{1}, ε_{2}, …, ε_{q−1} be the set of all q − 1 edges with the common vertex v = τ(ε), numbered such that the angles between the consecutive edges are 2π/q. Because q − 1 = 2m, ε_{q−1} ∈ E_{k−2}^{2,q−1}. Let Δ ∈ NP_{k−2} be the polygon containing ε; then, Δ_{1} = ρ_{ε}(Δ) and Δ_{2} = ρ_{ε_{q−1}}(⋯ (ρ_{ε_{2}}(Δ)) ⋯) have a common edge ε′ of type (3, q). The other distinct edge of Δ_{1} adjacent to ε′ is an edge of (k − 1)-type (3, 4).

In short, each ε ∈ NE_{k−2}^{2,q−1} generates

1 edge = ε ∈ E_{k−1}^{4,q},

\frac{1}{2} edge ∈ NE_{k−1}^{3,q},

1 edge ∈ NE_{k−1}^{3,4} .

(69)

The edges of NE_{k−1}^{3,q} will not contribute with new edges. For ε ∈ NE_{k−2}^{3,4}, let v_{k−2}^{3} be the initial vertex of ε, and let ε′ be the other edge of NE_{k−2}^{3,4}, also with initial vertex in v_{k−2}^{3}. The reflection in ε will originate a new edge of NE_{k−1}^{2,5}, because we will have another new edge with a vertex in v_{k−2}^{3}, which will appear in the reflection in ε′, and a new edge of NE_{k−1}^{2,6}. In short, each ε ∈ NE_{k−2}^{3,4} generates

1 edge = ε ∈ E_{k−1}^{5,6},
1 edge ∈ NE_{k−1}^{2,5},
1 edge ∈ NE_{k−1}^{2,6} .

(70)

Now, for j = q, if ε ∈ NE_{k−2}^{2,q}, let ε = ε_{1}, ε_{2}, …, ε_{q} be the set of edges with the same final vertex as ε. Because the angle between ε_{1} and ε_{q} is 2π/q, the reflection in ε will generate the same polygon as the reflection in ε_{q}. Thus, ε will only generate

1 edge = ε ∈ E_{k−1}^{4,q},

\frac{1}{2} edge ∈ NE_{k−1}^{4,4} .

(71)

Finally, if ε ∈ NE_{k−2}^{4,4}, the reflection in ε will generate two new edges, that is,

1 edge = ε ∈ E_{k−1}^{6,6},

2 edges ∈ NE_{k−1}^{2,6} . (72)

We can then prove the following result.

Theorem 9. Let {p, q} be a tessellation with p = 3, q = 2m + 1, m ≥ 2 and k ≥ 2, all of which are integers. Then, for the two initial levels, we have | NE_{0}^{2,2} | = | E_{0} | = 3; in addition, we have | NE_{0}^{i,j} | = 0 for (i, j) ≠ (2, 2), | NE_{1}^{2,4} | = 2p, | NE_{1}^{2,j} | = 0 for j ≠ 4, and for the other levels

| NE_{k−1}^{2,4} | = ∑_{j=2}^{m−1} | NE_{k−j}^{2,4} | + ∑_{j=2}^{m−1} | NE_{k−j−1}^{3,4} |  (73)
| NE_{k−1}^{2,2j+1} | = | NE_{k−(j−1)}^{2,5} |, for 3 ≤ j ≤ m  (74)
| NE_{k−1}^{3,q} | = \frac{1}{2}| NE_{k−2}^{2,q−1} |  (75)
| NE_{k−1}^{3,4} | = | NE_{k−2}^{2,q−1} |  (76)
| NE_{k−1}^{4,4} | = \frac{1}{2}| NE_{k−j−2}^{3,4} |  (77)
| NE_{k−1}^{2,6} | = 2| NE_{k−2}^{4,4} | + | NE_{k−2}^{3,4} |  (78)
| NE_{k−1}^{2,5} | = | NE_{k−2}^{3,4} |  (79)

where | NE_{k−j}^{2,4} | = | NE_{k−j}^{2,5} | = 0 for k ≤ j.

The total at level k is

| NE_{k} | = (2 + 2f_{m}(3) + \frac{3}{2}f_{k−1}(m − 2)f_{4}(m))| NE_{k−2}^{2,4} | + 2f_{m}(3)| NE_{k−3}^{2,4} | + 4f_{m}(4) ∑_{j=4}^{m−2} | NE_{k−j}^{2,4} |

+ (4f_{m}(4) + \frac{3}{2}f_{k−1}(m − 2)f_{m}(3))| NE_{k−m+1}^{2,4} |

+ 2(f_{k}(m) + f_{k−1}(m))f_{m−1}(2)f_{m−1}(3) ∑_{j=3}^{m−2} | NE_{k−j−1}^{3,4} |

+ 2((f_{k}(m) + f_{k−1}(m))f_{m−1}(2) + f_{m}(3)f_{k−2}(m − 1))| NE_{k−3}^{3,4} |

+ (2f_{k}(m) + 2f_{k−1}(m) + \frac{1}{2}f_{k−1}(2m − 2))| NE_{k−m}^{3,4} | + f_{m}(3)f_{k−2}(m + 2)| NE_{k−m−3}^{3,4} |

+ f_{k−1}(m − 1)(2f_{m}(3) + \frac{3}{2}f_{k−1}(m − 2)f_{4}(m))| NE_{k−2}^{3,4} |

+ 2f_{k−1}(m − 1)| NE_{k−1}^{3,4} | + f_{k−1}(m + 2)| NE_{k−m−1}^{3,4} | .

Proof. Applying together the information of the edges of the same type from the relations (56) and (69) with (72), and because q − 3 = 2m + 1 − 3 = 2(m − 1), it follows that

| NE_{k−1}^{2,4} | = ∑_{j=4}^{q−2} | NE_{k−2}^{2,j} | = ∑_{j=2}^{m−1} | NE_{k−2}^{2,2j} | + ∑_{j=2}^{m−1} | NE_{k−2}^{2,2j+1} |  (80)
| NE_{k−1}^{2,j+2} | = | NE_{k−2}^{2,j} |, for 4 ≤ j ≤ q − 2  (81)
| NE_{k−1}^{3,q} | = \frac{1}{2}| NE_{k−2}^{2,q−1} |  (82)
| NE_{k−1}^{3,4} | = | NE_{k−2}^{2,q−1} |  (83)
| NE_{k−1}^{4,4} | = \frac{1}{2}| NE_{k−2}^{2,q} |  (84)
| NE_{k−1}^{2,6} | = 2| NE_{k−2}^{4,4} |  (85)
| NE_{k−1}^{2,6} | = | NE_{k−2}^{3,4} |  (86)
| NE_{k−1}^{2,5} | = | NE_{k−2}^{3,4} |  (87)

The relation (81) is fundamental, and we obtain

| NE_{k−2}^{2,2j} | = | NE_{k−j}^{2,4} |  (88)
| NE_{k−2}^{2,2j+1} | = | NE_{k−j}^{2,5} | ,  (89)

for 3 ≤ j ≤ m. Combining (89) with (87) and (84), we obtain the important relations

| NE_{k−2}^{2,2j+1} | = | NE_{k−j−1}^{3,4} |, for 2 ≤ j ≤ m  (90)
| NE_{k−2}^{4,4} | = \frac{1}{2}| NE_{k−j−2}^{3,4} | .  (91)

Using these relations in (80) − (87), we obtain the formulae (73) − (79) in the theorem.

Because we are considering k ≥ 2, different types of edges will appear as k increases. Then, the edges of type (3, 4) appear for the first time for k = m, (2, 5) for k = m + 1, (4, 4) for k = m + 3, (2, q − 1) for k = m − 1, and (2, q) for k = 2m − 1. These relations are important because they determine the functions f that control the appearance of these edges.

From the relations (80) − (87), we see that several different kinds of edges at level k − 2 give origin to edges of type (2 − 6). Thus, the total of these edges is

| NE_{k−2}^{2,6} | = | NE_{k−3}^{2,4} | + \frac{f_{k−2}(m + 2)}{2}| NE_{k−m−3}^{3,4} | + f_{k−2}(m − 1)| NE_{k−3}^{3,4} | .

Another delicate point occurs when q = 7, because we have q − 1 = 6. Then, we need to separate the cases | NE_{k}^{2,q−1} | and | NE_{k}^{2,6} |. In short, we have

| NE_{k−1}^{3,4} | = f_{m}(3)| NE_{k−m}^{2,4} | + f_{4}(m)| NE_{k−2}^{2,6} | .

For the general formula for | NE_{k} |, we must be more careful, because it is the most involved case.

Let ε ∈ NP_{k−1} be an external edge of (k − 1)-type (2, j). We assume that j ≤ q − 2. The edge ε is an edge of an external polygon Δ. Because j ≤ q − 2, the reflected polygon Δ′ = ρ_{ε}(Δ) will have all but ε as an external edge. That is, ε will give rise to (p − 1) = 2 distinct edges in NE_{k}.

If j = q −1, given an edge ε_{1} ∈ E_{k−1}^{2,q−1}, there is another edge ε_{2} ∈ E_{k−1}^{2,q−1} joining a common vertex. Considering (for i = 1, 2) Δ_{i} as a polygon in P_{k−1}, such that ε_{i} is an (exterior) edge of Δ_{i}, we find that ε = ρ_{ε_{1}}(Δ_{1}) ∩ ρ_{ε_{2}}(Δ_{2}); thus, each of these edges ε_{1} and ε_{2} contribute along with (p − 2) = 1 new external edges at level k, in addition to ε. Now, ε is also a new edge of type (3, q) in | NE_{k} |, and the total number of edges must also be computed. Because ε_{1} and ε_{2} give origin to the same edge, each one contributes with \frac{1}{2} edge, in for a total of 1 + \frac{1}{2} = \frac{3}{2} new edges.

If j = q, we have the same situation as above, where ε will contribute with \frac{1}{2} new edge of type (4, 4). For (i, j) = (3, 4), let Δ be the polygon in NP_{k−1} such that ε is an external edge. The reflection of ε in Δ will give two new edges in E_{k}.

Finally, if (i, j) = (4, 4), the reflection in ε will give origin to two new edges. Then, we have

| NE_{k} | = 2 ∑_{j=4}^{q−2} | NE_{k−1}^{2,j} | + \frac{3}{2}f_{k−1}(m − 2)(f_{m}(3)| NE_{k−1}^{2,q−1} | + f_{4}(m)| NE_{k−1}^{2,6} |)

+ \frac{1}{2}f_{k−1}(2m − 2)| NE_{k−1}^{2,q} | + 2f_{k−1}(m − 1)| NE_{k−1}^{3,4} | + 2f_{k−1}(m + 2)| NE_{k−1}^{4,4} | . (92)

The term (f_{m}(3)| NE_{k−1}^{2,q−1} |+f_{4}(m)| NE_{k−1}^{2,6} |) in the formula is used for control when q = 7. Applying together all relations in (92), we obtain the expression in the theorem.

4 Acknowledgment

The authors would like to thank the anonymous referee for the helpful suggestions and comments.

References

[1] C. D. Albuquerque, R. Palazzo Jr., and E. B. Silva, Topological quantum codes on compact surfaces with genus g ≥ 2, J. Math. Phys., 50 (2009), 023513.

[2] L. Bartholdi and T. G. Ceccherini-Silberstein, Growth series and random walks on some hyperbolic graphs, Monatsh. Math., 136 (2002), 181–202.

[3] A. F. Beardon, The Geometry of Discrete Groups, Springer, 1983.

[4] J. W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata, 16 (1984), 123–148.

[5] J. W. Cannon and P. Wagreich, Growth functions of surface groups, Math. Ann., 293 (1992), 239–257.

[6] W. J. Floyd and S. P. Plotnick, Growth functions for semi-regular tilings of the hyperbolic plane, Geom. Dedicata, 53 (1994), 1–23.

[7] R. Grigorchuk and P. De La Harpe, On problems related to growth, entropy, and spectrum in group theory, J. Dyn. Control Syst., 3 (1997), 51–89.

[8] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge, 1990.

[9] E. B. Silva, M. Firer, and R. Palazzo Jr., Counting domains in {p, q} tessellations, Appl. Math. Lett., 16 (2003), 323–328.

[10] E. B. Silva, S. R. Costa, M. Firer, and R. Palazzo Jr., Signal constellations in the hyperbolic plane: A proposal for new communication systems, J. Franklin Inst., 343 (2006), 69–82.

[11] D. Sullivan, The density at infinity of a discrete group of hyperbolic motions, Publ. Math. Inst. Hautes Etudes Sci., 50 (1979), 171–202.

[12] G. Ungerboeck, Trellis-coded modulation with redundant signal sets part I: introduction, IEEE Comm. Magazine, 2 (1987), 5–11.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05B45, 52C20. Keywords: hyperbolic geometry, tiling, enumeration, counting edges, polygon.

Received January 26 2016; revised versions received August 7 2017; September 9 2017; November 18 2017. Published in Journal of Integer Sequences, November 19 2017.

Return to Journal of Integer Sequences home page.