\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\DeclareMathOperator{\NV}{NV}
\DeclareMathOperator{\NE}{NE}
\DeclareMathOperator{\NP}{NP}
\DeclareMathOperator{\V}{V}
\DeclareMathOperator{\E}{E}
\DeclareMathOperator{\PP}{P}
\DeclareMathOperator{\C}{C}
\DeclareMathOperator{\B}{B}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Enumeration of Vertices, Edges and Polygons \\
\vskip .1in
in Tessellations of the Plane
}
\vskip 1cm
Marcelo Firer\\
Imecc --- Unicamp \\ 
Rua S\'{e}rgio Buarque de Holanda 651 \\
13083-859 Campinas --- SP \\
Brazil \\
\href{mailto:mfirer@ime.unicamp.br}{\tt mfirer@ime.unicamp.br} \\
\ \\
Karine Bobadilha Couto \\ 
Fatec --- Catanduva \\ 
Rua Maranh\~{a}o 898 \\
15800-020 Catanduva --- SP \\
Brazil \\ 
\href{mailto:karinebobadilha@yahoo.com.br}{\tt karinebobadilha@yahoo.com.br} \\ 
\ \\
Eduardo Brandani da Silva\footnote{Partially funded by a grant from Fapesp (2014/25463-6).} \\ 
Department of Mathematics \\
Maringa State University \\ 
Av.\ Colombo \\ 
5790 Maringa, PR \\
Brazil \\ 
\href{mailto:ebsilva@wnet.com.br}{\tt ebsilva@wnet.com.br} 
\end{center}

\vskip .2 in

	

\begin{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 {\it$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.
\end{abstract}

\section{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 $\Delta$ of the tessellation. Considering the Cayley metric $d(\cdot , \cdot )$ of the group $(G,S)$, we denote by $\| g \|=d(g,e)$ the \text{norm} of an element $g\in G$. For a given positive integer $n$ we consider the image of $\Delta$ under the $n$-ball,
\[
\B_n(\Delta ) = \{ g(\Delta ); \| g\| \leq n \},
\]
and ask the following natural questions:
\begin{enumerate} 
	\item How many faces (polygons) are there in $\B_n(\Delta )$?
	\item How many polygons edges are there in $\B_n(\Delta )$?
	\item How many polygons vertices are there in $\B_n(\Delta )$?
\end{enumerate}

The first question is equivalent to asking about the growth sequence $\{ \PP_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 $\left(X,d\right)$, 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 \cite{harpe}, 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 $\sum_{n=0}^{\infty }a_n t^n$, where the coefficient $a_n$ denotes the number of elements within distance $n$ from the identity element. Cannon \cite{Ca1,Ca2} also considered the growth series of tessellations related to the surfaces of genus $g \geq 2$, which do not include all possible tessellations of the hyperbolic plane. These results were generalized by Floyd and Plotnik \cite{Floyd} and Bartholdi and Ceccherini-Silberstein \cite{bartholdi}, 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\pi/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.\ \cite{BFP} 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 $\ref{prop1}$ and $\ref{prop2}$. 

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 $\mathbb{R}^n$, which becomes a signal constellation, after taking a convenient quotient using a sublattice $A' \subset A$. One of the most important of such possibilities is considering the constellations of points in the hyperbolic plane. Silva et al.\ \cite{Brandani2006} 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 $\mathbb{R}^n$.

Albuquerque et al.\ \cite{Albuquerque2009a} 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 \cite{Ungerboeck1987} introduced a very important modulation technique for communication systems using a Euclidean case of the sets considered here.


\section{Growth of hyperbolic tessellations}

Let us consider in the hyperbolic plane $\mathbb{H}^{2}$ a regular polygon $\mathcal{P}_{p,q}$ that has $p$ equal-length edges, and where all $p$ internal angles are equal $\frac{2\pi}{q}$. From Poincar\'e'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 $\mathbb{H}^{2}$ with $\mathcal{P}_{p,q}$, in the sense that there is a family $ \{  \mathcal{P}_{n}|n\in \mathbb{N} \}  $ of
isometric copies of $\mathcal{P}_{p,q}$, such that $\mathbb{H}^{2} = \cup
_{n\in \mathbb{N}}\mathcal{P}_{n}$. When $\mathcal{P}_{n}\cap
\mathcal{P}_{m}\neq \emptyset$, this intersection is either a common edge or a
common vertex. We say that the family $\mathcal{T}_{p,q}=\{  \mathcal{P}_{n}|n \in
\mathbb{N} \}  $ defines a tessellation (or tiling) and each $\mathcal{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 $\mathcal{T}_{p,q}$ by $\mathcal{E}_{p,q}$ and $\mathcal{V}_{p,q}$, respectively. See Beardon \cite{Be} 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
$\mathcal{P}$ and $\mathcal{P}^{\prime}$, we consider points $x$ and
$x^{\prime}$ contained in the interior of the tiles. Let $\gamma$ be a
path connecting the given points, that is, $\gamma:[0,1]
 \rightarrow \mathbb{H}^{2}$ is a continuous map, such that $\gamma (
0 )  = x$ and $\gamma (  1)  = x^{\prime}$. If no vertex of the
tiling is contained in the image of $\gamma$, we say that $\gamma$ is a
regular path. Let $| \gamma |$ be the number of
edges of the tilling crossed by $\gamma$:%
\[
| \gamma | := | \{  \varepsilon\in
\mathcal{E}_{p,q} \,|\, \varepsilon\cap\gamma (  [  0,1 ]  )
\neq\emptyset \} | \, ,
\]
where $| X | $ throughout the current paper denotes the
cardinality of the set $X$. We define%
\begin{eqnarray*}
d (  \mathcal{P},\mathcal{P^{\prime}} )   &: = &\inf\{
| \gamma \,|\, \gamma\text{ is a regular path connecting
}x\text{ to }x^{\prime} \} \\
&  = &\min\{  | \gamma \,|\, \gamma\text{ is a regular path
connecting }x \text{ to }x^{\prime} \}  .%
\end{eqnarray*}

The above defines a metric in a set of tiles. It is well known that the tiling $\mathcal{T}_{p,q}$ has exponential growth, that is, there are constants $M, \alpha \in \mathbb{R}$, $b\in \mathbb{N}$ with $M,\alpha
>0$, $b>1$, such that
\[
0 < \lim_{n \rightarrow\infty}\frac{\vert \B_{n}(\mathcal{P})\vert}{M b^{\alpha n}} < \infty \,,
\]
where $\B_{n}(\mathcal{P})  = \{\mathcal{P}^{\prime} \in \mathcal{T}_{p,q} : d(\mathcal{P},\mathcal{P}^{\prime}) \leq n\}$ is the ball (in $\mathcal{T}_{p,q}$) centered on $\mathcal{P}$, with radius $n$ (see Sullivan \cite[Proposition 3]{Sullivan}).

Let $\Delta_{0}$ be the initial tile of our tessellation, and $p_{0}$ be its barycenter. The geodesics of $\mathbb{H}^{2}$, containing the edges
of $\Delta_{0}$, are called support geodesics of the tile.
Each geodesic $\delta_{i}, i=1,\ldots,p$ determines a unique reflection
$\rho_{i}$ (involutive isometry of $\mathbb{H}^{2}$ that has the geodesic as
a set of fixed points). We let $\Gamma_{p,q}$ denote the group generated by
$ \{  \rho_{1},\ldots,\rho_{p} \}  $. The group $\Gamma_{p,q}$ is a discrete group of isometries that has $\Delta_{0}$ as a fundamental Dirichlet domain
centered at $p_{0}$, and thus
\[
\Delta_{0}= \{  x \in \mathbb{H}^{2} \,|\, d(x,p_{0}) \leq d(f(x),p_{0}) , \forall f\in\Gamma_{p,q} \} \, ,
\]
and every tile $\Delta_{n}\in\mathcal{T}_{p,q}$ is an image $f(\Delta_{0})$ for a unique $f\in\Gamma_{p,q}$. If we consider the Cayley metric  $d_{\mathcal{C}}(\cdot,\cdot)$ on $\Gamma_{p,q}$ determined by the set $\{\rho_{1},\ldots,\rho_{p}\}$ of generators, we find that
\begin{equation}
d(f(\Delta_{0}),h(\Delta_{0})) = d_{\mathcal{C}}(f,h)  , \forall f,h \in \Gamma_{p,q}\text{.}
\label{equiv}%
\end{equation}

We will now introduce a few concepts and definitions. We consider the set of reflections at the edges of the regular polygon $\Delta_{0}$ (with $p$ edges and angles equal to $\frac{2\pi}{q}$) as a standard set of generators of the group $\Gamma_{p,q}$. A geodesic $\delta$ is a support geodesic of the tessellation if an edge of a tile of the tessellation $\mathcal{T}_{p,q}$ is contained in
$\delta$. Let $S$ be the set of all support geodesics, and $\delta\in S$ if, and only if, $\rho_{\delta}$ is a reflection contained in the group $\Gamma_{p,q}$.

Because $d(g(\Delta_{0}),h(\Delta_{0})) = d_{\mathcal{C}}(g,h) , \forall
g,h \in \Gamma_{p,q}$, we can consider metric constructions in $\mathcal{T}_{p,q}$ or in $\Gamma_{p,q}$ without a distinction.

Let $\B_{k}$ be the closed ball in $\Gamma_{p,q}$ with the center in the
identity and radius $k$, and let $\C_{k}:= \B_{k}\setminus \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 \in \Gamma_{p,q} \,|\, d_{\mathcal{C}}(g,e) \leq k \}$ and $\C_{k} := \{g \in \Gamma_{p,q} \,|\, d_{\mathcal{C}}(g,e) = k\}$.

From the correspondence between the elements of the group and the polygons of
the tessellation, we let $\PP_{k}$ denote the set of polygons of the tessellation
corresponding to the ball $\B_{k}$ in the group, and by $\NP_{k} := \PP_{k}\setminus
\PP_{k-1}$ the set corresponding to the circumference $\C_{k}$, where the prefix $N$
stands for {\it new}: $\PP_{k} = \{ g(\Delta_{0}) \,|\, g \in \B_{k}\}$ and $\NP_{k}  = \{g(\Delta_{0}) \,|\, g \in \C_{k} \}$.

Naturally, we have $|\PP_{k}|=|\B_{k}|$, $|\NP_{k}| = |\C_{k}|$ where $|\PP_{k}|$, the cardinality of $\PP_{k}$, is the $k$-th coefficient of the growth series of the group $\Gamma_{p,q}$. Our goal is to obtain a recursive enumeration for $\PP_{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 $\PP_{k}$, and $\E_{k}$ denote the set of edges of polygons in $\PP_{k}$. In a similar way, we let $\NE_{k}:=E_{k}\setminus \E_{k-1}$ and $\NV_{k}:= \V_{k}\setminus \V_{k-1}$ denote the sets of the new vertices and edges in the tessellation, respectively. Clearly, we then have
\begin{equation}
\label{eq2}
|\V_{k}|=\sum_{i=0}^{k}|\NV_{i}|,~~~|\E_{k}|=\sum_{i=0}^{k}|\NE_{i}%
|~~~\text{and}~~~|\PP_{k}|=\sum_{i=0}^{k}|\NP_{i}| \, ,
\end{equation}
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  $\Gamma_{p,q}$.

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

We define the function $t_{k} : \V_{k}\rightarrow\{2,\ldots,q\}$, which for each
vertex $v\in \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}},\ldots,v_{k,|\V_{k}|}^{w_{|\V_{k}|}%
}\}~~\text{and}~~\NV_{k}=\{v_{k,1}^{w_{1}},v_{k,2}^{w_{2}},\ldots,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,\ldots,|\V_{k}|$ for $\V_{k}$, and $i=1,\ldots,|\NV_{k}|$ for
$\NV_{k}$.

Considering an edge $\varepsilon\in \E_{k}$, we characterize it using the $k$-type of both its vertices: We state that $\varepsilon$ has $k$-type $(t_{k}(\iota(\varepsilon),t_{k}(\tau(\varepsilon))))$,
where $\iota(\varepsilon)$ and $\tau(\varepsilon)$ are the initial and final
vertices, respectively, which determine $\varepsilon$. It is assumed that
$t_{k}(\iota(\varepsilon))\leq t_{k}(\tau(\varepsilon))$, and, without
ambiguity, we can assume the notation $\varepsilon_{k}^{i_{j},w_{j}}$, where
$i_{j}=t_{k}(\iota(\varepsilon))$ and $w_{j}=t_{k}(\tau(\varepsilon))$, with
$j=1,\ldots,|\E_{k}|$ for $\E_{k}$ and $j=1,\ldots,|\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}=\{\varepsilon_{k,1}^{i_{1},w_{1}},\varepsilon_{k,2}^{i_{1},w_{1}%
},\ldots,\varepsilon_{k,|\E_{k}|}^{i_{|\E_{k}|},w_{|\E_{k}|}}\} \, ; \, \NE_{k}
=\{\varepsilon_{k,1}^{i_{1},w_{1}},\varepsilon_{k,2}^{i_{2},w_{2}%
},\ldots,\varepsilon_{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}\backslash \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 $\varepsilon :=\varepsilon_{k,j}^{i_{j},\tau_{j}}$
has $\tau_{j}=q$ edges adjacent to its terminal vertex, we state that the edges with $\tau (\varepsilon )$ as a vertex, are a closed cycle of edges if there are also $q$ polygons in $\PP_k$ with $\tau (\varepsilon )$ as a vertex. We note that $\tau_{j}=q$ does not imply that we have a closed cycle of edges at $\tau_{j}$, because there can be an outer edge among the $q$ edges. If $\varepsilon_{k,j}^{i_{j},\tau_{j}}$ is an outer edge, then, the reflection $\rho_{\varepsilon_{k,j}^{i_{j},\tau_{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}\in \V_{k}$ and $\mathcal{A}:=\mathcal{A}(v_{k,t}^{j}) = \{\varepsilon_{k,1}^{i_{1},\tau_{1}},\ldots,\varepsilon_{k,j}^{i_{j},\tau_{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 $\mathcal{A}$ has one, and,  consequently, at least, two exterior edges. Thus, we assume that the ordinance of the edges of $\mathcal{A}$ is applied in such a way that $\varepsilon_{k,1}^{i_{1},\tau_{1}}$ and
$\varepsilon_{k,j}^{i_{j},\tau_{j}}$: The first and last edges are
$k$-exterior edges. Such an ordering of $\mathcal{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\pi}{q}$. If $\varepsilon_{k,i}^{i_{i},\tau_{i}}$ and $\varepsilon
_{k,i+1}^{i_{i+1},\tau_{i+1}}$ are consecutive, for all $i=1,2,\ldots,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 {\it hole}, at the edges containing
$v_{k,t}^{j}$.

Given a set of consecutive edges $\mathcal{A}=\{\varepsilon_{k,1}^{i_{1}	,\tau_{1}},\varepsilon_{k,2}^{i_{2},\tau_{2}},\ldots,\varepsilon_{k,j}^{i_{j},\tau_{j}}\}$ of the vertex $v_{k,t}^{j}$, only the $k$-exterior edges
of $\mathcal{A}$ are $\varepsilon_{k,1}^{i_{1},\tau_{1}}$ and $\varepsilon
_{k,j}^{i_{j},\tau_{j}}$ because the edges $\varepsilon_{k,2}^{i_{2},\tau_{2}%
},\ldots,\varepsilon_{k,j-1}^{i_{j-1},\tau_{j-1}}$ are the edges of two tiles.

Let $\alpha_{1},\cdots,\alpha_{p}$ be geodesics supporting the edges of
the initial polygon $\Delta_{0}$ of the tessellation. The group
$\Gamma_{p,q}$ is generated by the reflections $\rho_{\alpha_{1}},\cdots
,\rho_{\alpha_{p}}$ in the support geodesics of the edges $\alpha_{1}%
,\cdots,\alpha_{p}$:
\[
\Gamma_{p,q}= \langle \newline\rho_{\alpha_{1}},\cdots,\rho_{\alpha_{p}%
} \rangle .
\]

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

Let $\delta$ be a support geodesic of the tessellation ($\rho_{\delta}%
\in\Gamma_{p,q}$). We state that $\delta$ separates the tiles $g(\Delta_{0})$
and $h(\Delta_{0})$ if they belong to different connected components of
${\bf H}^{2}\backslash\delta$, that is, every continuous path connecting
these polygons intercepts $\delta$.

Let $\varepsilon$ be an edge of the tessellation with initial vertex $v$ and
$\delta$ as its support geodesic. We let $\delta_{i}^{+}$ denote the geodesic ray
with the initial point in $v$ and containing $\varepsilon$, and $\delta_{i}^{-}$ as
its opposite ray.

Given a support geodesic of the tessellation $\delta\in S$ and $\Delta
_{i},\Delta_{j}\in \PP_{k}$, we consider the following notation:
\[
\Delta_{i}~|_{\delta}~\Delta_{j}%
:=\text{ $\delta$ separates the polygons $\Delta_{i}$ and $\Delta_{j}$},
\]%
\[
\Delta_{i} \nmid_{\delta}\Delta_{j}%
:=\text{ $\delta$ does not separate the polygons $\Delta_{i}$ and
	$\Delta_{j}$} .
\]

In the following results, we consider an initial polygon $\Delta_{0}$ with edges $\varepsilon_{0,1}^{2,2},\cdots,\varepsilon_{0,p}^{2,2}$, and the group
$\Gamma_{p,q} = \langle\rho_{\varepsilon_{0,1}^{2,2}},\cdots,\rho_{\varepsilon	_{0,p}^{2,2}}\rangle$ generated by the reflections in these edges.

\begin{proposition}
	\label{prop1} Let $\{p,q\}$ be a tessellation of ${\bf H}^2$. If $q$ is even, then the $k$-type of a vertex is always even.
\end{proposition}

\begin{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 $\Delta_{0}$ has vertices  $v_{0,1}^{2},\cdots,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. 
\end{proof}

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

\begin{proposition}
	\label{prop2}Consider a $\mathcal{T}_{p,q}$ tessellation and let $v_{k}^{i}\in
	\V_{k}$. If $q$ is even, then $v_{k}^{i}\in \NV_{k}$ if, and only if, $i=2$. If $q$ is odd, then $v_{k}^{i}\in \NV_{k}$, if, and, only if, either $i=2$ or $i=3$, and, when $i = 3$ there is an edge $\varepsilon$ with $v=i(\varepsilon)$ and $t_{k}(\tau(\varepsilon)) = q$.
\end{proposition}

\begin{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}\in \V_{k}$, with $i=2$, we suppose $v_{k,l}^{i}\not \in \NV_{k}$, that is, $v_{k,l}^{i}\in \NV_{t}$ for some $t<k$.
		Through Proposition \ref{prop1}, 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\}\geq2$, which is absurd.
		
Further, let us consider $v = v_{k-1,l}^{i}\in \NV_{k}$. We suppose $i\neq 2$. Through Proposition \ref{prop1}, $i$ is even, then $i\geq4$, let us enumerate counterclockwise the edges of $v_{k-1,l}^{i}$. Because it is a set of 	consecutive edges, we can write $\varepsilon_{k-1,1}^{i,\tau},\varepsilon_{k-1,2}^{i,\tau},\ldots,\varepsilon_{k-1,i}^{i,\tau}$. Only the $(k-1)$-outer edges are $\varepsilon_{k-1,1}^{i,\tau}$ and $\varepsilon_{k-1,i}^{i,\tau}$. We label the polygons containing these edges as $\Delta_{1},\Delta_{2},\ldots,\Delta_{i-1}$, with $\Delta_{j}$ containing the edges $\varepsilon_{k-1,j}^{i,\tau}$ and $\varepsilon_{k-1,j+1}^{i,\tau}$, for $j=1,\ldots,i$.
		
		Thus, $\Delta_1$ and $\Delta_{i-1} \in \NP_{k-1}$. To conclude the proof, it is sufficient to show that $\Delta_2$ (and $\Delta_3,\cdots,\Delta_{i-2}$) $\in \PP_{k-1}$. Indeed, if $\Delta_2 \in \PP_r$, then $\Delta_2 \in \NP_r$, $r \leq k$. If $\varepsilon_2, \varepsilon_3 \in \NP_r$, then $\iota(\varepsilon_2) = \iota(\varepsilon_3) = v \in \NP_r$, contradicting the hypothesis of $v \in \NP_{k+1}$, because $\NP_r \cap \NP_{r+1} = \emptyset$.
		
		If we suppose that $\Delta_2 \notin \PP_{k-1}$, then $\Delta_2 \in \NP_k$. Because both $\Delta_1$, $\Delta_2 \in \NP_k$, there are $\Delta_1^-$, $\Delta_2^- \in \NP_{k-1}$ such that $\rho_{\delta_1}(\Delta_1^-) = \Delta_1$ and $\rho_{\delta_2}(\Delta_2^-) = \Delta_2$, where $\delta_i = \Delta_i \cap \Delta_i^-$ is an edge and $\rho_{\delta_i}$ is the reflection in the geodesic containing $\varepsilon_i$.
		
		Recall that $\varepsilon_2 = \Delta_1 \cap \Delta_2$ (because the edges are consecutive). The edge $\varepsilon_1$ is the first segment of a line connecting the common vertex $\{v\} = \cap_{j=1}^i \varepsilon_j$ to $\PP_{k-1}$ along the boundary of $\Delta_1$. There is also a line connecting $v$ to $\PP_{k-1}$, such that it has $\varepsilon_l$ as an initial segment. This gives rise to a $k$-hole, unless $\varepsilon_1 = \varepsilon_i$. However, in this case, we changed the parity of vertices $v$ when passing from stage $k-1$ to stage $k$, contradicting Proposition \ref{prop1}. We thus conclude the proof.
\end{proof}

We should keep in mind that the given edge $\varepsilon_{k}^{i,\tau}\in \E_{k}$, $i(\varepsilon_{k}^{i,\tau})$ and $\tau(\varepsilon_{k}^{i,\tau})$ denote the initial and final vertices of $\varepsilon_{k}^{i,\tau}$, respectively. We can then define the following set:
\begin{equation}
n_{k}(\varepsilon_{k}^{i,\tau}) = \vert\{\Delta \in \PP_{k} \,|\, \iota(\varepsilon_{k}^{i,\tau})\in\Delta\}\vert ,
\label{iota}%
\end{equation}
that is, $n_{k}(\varepsilon_{k}^{i,\tau})$ is the cardinality of polygons in the tessellation having in common the initial vertex of the edge  $\varepsilon_{k,l}^{i,\tau}$.

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

\begin{proposition}
	\label{prop3} Let $\varepsilon=\varepsilon_{k}^{2,\tau}\in \NE_{k}$. Then,
	$n_{k}(\varepsilon)=1$ and $n_{k+1}(\varepsilon)=3$.
\end{proposition}

\begin{proof}
	Let $v=\iota(\varepsilon)$. Because $v$ has $k$-type $2$, there is another edge
	$\varepsilon^{\prime}\in \V_{k}$, such that $\iota(\varepsilon^{\prime}) = v$. It follows that $\varepsilon$ and $\varepsilon^{\prime}$ are
	edges of the same polygon $\Delta\in \PP_{k}$, and hence, $n_{k}(\varepsilon)=1$.
	Because both $\iota(\varepsilon)$ and $\iota(\varepsilon^{\prime})$ have
	$k$-type $2$, we have $\varepsilon,\varepsilon^{\prime}\in \NE_{k}$. Both will give rise to new polygons in the next stage, such that
	$n_{k+1}(\varepsilon)=3$. We thus conclude the proof.\hfill
\end{proof}

If $\varepsilon_{k}^{2,\tau}$ is a $k$-outer edge, then it contributes with
a new polygon at the level $k+1$. If $\tau<q$, then each reflection in the edges
with the same vertex will generate different tiles. However, if $\tau=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=\iota(\varepsilon_{k}^{2,\tau})$ will have $k+1$-type $4$. In the special
case in which $p=3$, it implies the existence of an edge $\varepsilon^{\prime} \in \NE_{k+1}$ of $k + 1$-type $(4,4)$. We have just proved the following:

\begin{corollary}
	\label{418}If $\varepsilon=\varepsilon_{k,l}^{i,\tau}\in \NV_{k}$, then
	$(i,\tau) = (2,\tau)$, except for the cases $\tau=q$ and $p=3$, in which $(i,\tau) = (4,4) \,$ can occur.
\end{corollary}

\section{Recursive counting functions for the growth of the group
$\Gamma_{p,q}$}

We consider the group $\Gamma_{p,q}$ generated by the reflections on the support geodesics of the edges of the regular polygon $\Delta_{0}$ with angles $\frac{2\pi}{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 $\Delta_{0}$. We obtain level $1$ by reflecting $\Delta_{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 $\Delta_{0}$ by  $g\in\Gamma_{p,q}$ with $\vert g \vert \leq k$, that is, any tile $\Delta \in \PP_{k}$ is in the form $g(\Delta_{0})$ for some $g \in \Gamma_{p,q}$, such that
\[
|g|_{C}=d_{C}(e,g) \leq k.
\]
Therefore, we have $ \vert \B_{k} \vert = \vert \PP_{k} \vert$, where $\B_{k}$ is the closed ball with radius $k$ and the center in the identity. In a similar manner, $\C_{k} = \B_{k}\setminus \B_{k-1}$ is the circumference with radius $k$ and the center in the identity. Thus, $\vert \C_{k} \vert = \vert \NP_{k} \vert$.

\subsection{Counting the polygons}

We want to find a recursive function for the growth of the group $\Gamma_{p,q}$.
It is sufficient to determine $ \vert \NP_{k} \vert $ for each $k \in \mathbb{N}$, because $|\PP_k| = \sum_{i = 0}^k |\NP_i|$, where $|\NP_0| = |\PP_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:
\begin{enumerate}
	\item[i)] $p > 3$ and $q = 2m$. 
\end{enumerate}
Only external edges (at level $k-1$) contribute towards new polygons at level $k$. Moreover, an edge $\varepsilon \in \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),\ldots,(2,q-2),(2,q)$. Each external edge of type $(2,2i)$, $i \leq m-1$ gives rise to a new polygon at the next level. Because $q = 2m$, for any edge $\varepsilon \in \NE_{k-1}^{2,q}$, there is another edge $\varepsilon' \in \NE_{k-1}^{2,q}$ with a common vertex $\tau(\varepsilon) = \tau(\varepsilon')$, and thus the reflection in $\varepsilon$ and $\varepsilon'$ gives rise to the same polygon. In other words, 
\begin{equation}
\label{eq4}
|\NP_k| = \sum_{i=1}^{m-1} |\NE_{k-1}^{2,2i}| + \frac{1}{2} |\NE_{k-1}^{2,q}| \, .
\end{equation}
\begin{enumerate}
	\item[ii)] $p = 3$ and $q = 2m$. 
\end{enumerate}
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,
\begin{equation}
\label{eq5}
|\NP_k| = \sum_{i=1}^{m-1} |\NE_{k-1}^{2,2i}| + \frac{1}{2} |\NE_{k-1}^{2,q}| + |\NE_{k-1}^{4,4}|\, .
\end{equation}
\begin{enumerate}
	\item[iii)] $p > 3$ and $q = 2m + 1 > 3$. 
\end{enumerate}
For any edge $\varepsilon \in \E_{k-1}^{2,j}$, with $j < q - 1$, the reasoning is the same as with the even case. If $\varepsilon \in \NE_{k-1}^{2,q-1}$, there are edges $\varepsilon'$ and $\varepsilon''  \in \NE_{k-1}^{2,q}$ that have a common vertex $\tau(\varepsilon) = \tau(\varepsilon') = \tau(\varepsilon'')$, and thus the reflection in $\varepsilon'$ and $\varepsilon''$ gives rise to two new polygons that have $\varepsilon$ as a common edge. Finally, for any edge $\varepsilon \in \NE_{k-1}^{2,q}$ there is another edge $\varepsilon' \in \NE_{k-1}^{2,q}$ with a common vertex $\tau(\varepsilon) = \tau(\varepsilon')$, and thus, the reflections in $\varepsilon$ and $\varepsilon'$ give rise to only one new polygon. It follows that
\begin{equation}
\label{eq6}
|\NP_k| = \sum_{i=2}^{q-1} |\NE_{k-1}^{2,i}| + \frac{1}{2} |\NE_{k-1}^{2,q}| \, .
\end{equation}
\begin{enumerate}
	\item[iv)] $p = 3$ and $q = 2m + 1$. 
\end{enumerate}
If we do not have edges of type $(2,2)$, edges of types $(3,4)$ and $(4,4)$ will appear. Thus, 
\begin{equation}
\label{eq7}
|\NP_k| = \sum_{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}| \, .
\end{equation}   
\begin{enumerate}
	\item[v)] $p \geq 6$ and $q = 3$. 
\end{enumerate}
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 $\varepsilon \in \NE_k^{2,3}$, there is $\varepsilon' \in \NE_k^{2,3}$, such that $\varepsilon$ and $\varepsilon'$ have a common vertex $v$, and the angle between them in $v$ is $2\pi/3$. Thus, the pair $\varepsilon, \varepsilon'$ will give an origin only to one new polygon. The total is
\begin{equation}
\label{eq8}
|\NP_k| = |\NE_{k-1}^{2,2}| + \frac{1}{2} |\NE_{k-1}^{2,3}| \, .
\end{equation}

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|$,.

\subsection{Counting the vertices}

We have determined the formulae for $ \vert \PP_{k} \vert $ 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$. 
\begin{enumerate}
	\item[i)] We suppose $p > 3$ and $q = 2m$, $m \geq 2$.  
\end{enumerate}
 For $k = 1$,
\begin{equation}
\begin{aligned}
&|\NV_1^2| = p (p - 2),   \\
&|\NV_1^4|  = p,   \\
&|\NV_1|  = p (p - 2) + p = |\NV_1^2| + |\V_0|.
\end{aligned}
	\end{equation}

In a general way, if $\varepsilon \in \NE_{k-1}^{2,j}$ with $j \leq q - 1$, then the reflection in $\varepsilon$ will be a new polygon $\Delta \in \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) \sum_{j = 2}^{q-1} |\NE_{k-1}^{2,j}|$ vertices of type $2$.

However, if $\varepsilon_1 \in \NE_{k-1}^{2,q}$, there exists $\varepsilon_2 \in \NE_{k-1}^{2,q}$, with a common vertex with $\varepsilon_1$, such that $\tau_{\varepsilon_1}(\Delta) = \tau_{\varepsilon_2}(\Delta)$. 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
\begin{equation}
\label{eq10}
|\NV_{k}^2| = (p - 2) \sum_{j = 2}^{q-1} |\NE_{k-1}^{2,j}| + (p - 3) \frac{|\NE_{k-1}^{2,q}|}{2} \,.
\end{equation}

Now, if $|\V_{k-1}|$ is known, then
\begin{equation}
\label{eq11}
|\V_k| = |\NV_{k}^{2}| + |\V_{k-1}| \,.
\end{equation}
\begin{enumerate}
	\item[ii)] $q = 2m + 1$, $m \geq 2$ and $p > 3$.  
\end{enumerate}
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 $\varepsilon \in \NV_{k - 1}^{2,j}$ with $3 < j < q-1$, the reflection in $\varepsilon$ is a new polygon $\Delta$ 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) \sum_{j = 2}^{q - 2} |\NE_{k-1}^{2,j}|$ vertices of type $2$.

However, if $\varepsilon \in \NE_{k-1}^{2,q-1}$, there exists $\varepsilon' \in \NE_{k-1}^{2,q-1}$ such that the reflections in $\varepsilon$ and $\varepsilon'$ give origin to distinct polygons, but with a common edge $\varepsilon_1 \in \NE_{k-1}^{3,q}$. Thus, $\varepsilon$ 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 $\varepsilon$ originates $\varepsilon_1 \in \NE_{k}^{2,3}$, we have a$1/2$ vertex of type $3$, totaling $1/2 |\NE_{k-1}^{2,q-1}|$ vertices of type $3$.

If $\varepsilon \in \NE_{k-1}^{2,q}$, there exists $\varepsilon_1 \in \NE_{k-1}^{2,q}$ with a common vertex with $\varepsilon$, such that $\tau_{\varepsilon}(\Delta) = \tau_{\varepsilon_1}(\Delta)$. 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
\begin{equation}
\label{eq12}
\begin{aligned}
&|\NV_{k}^2| = (p - 2) \sum_{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}   . 
\end{aligned} 
\end{equation}
The total of level $k$ is given by 
\begin{equation}
\label{eq13}
|\V_k| = |\NV_{k}^{2}| + |\NV_{k}^{3}| + |\V_{k-1}| \,.
\end{equation}
\begin{enumerate}
	\item[iii)] $p = 3$ and $q = 2m$.  
\end{enumerate}
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,
\begin{equation}
\label{eq14}
|\NV_{k}^2| = \sum_{j = 4}^{q-2} |\NE_{k-1}^{2,j}| + |\NE_{k-1}^{4,4}| \,.
\end{equation}
Equation $(\ref{eq11})$ provides the total.
\begin{enumerate}
	\item[iv)] $p = 3$ and $q = 2m + 1$.  
\end{enumerate}
The edges of type $(2,j)$ with $4 \leq 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,
\begin{equation}
\label{eq15}
\begin{aligned}
&|\NV_{k}^2| = \sum_{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} \, , 
\end{aligned} 
\end{equation}
where Equation $(\ref{eq13})$ gives the total.
\begin{enumerate}
	\item[v)] $p \geq 6$ and $q = 3$.  
\end{enumerate}
For $k = 1$, we have
\begin{equation}
\label{eq16}
\begin{aligned}
&|\NV_1^2| = p (p - 4), \\
&|\NV_1^3| = p,  \\
&|\NV_1| = p (p - 4) + p = |\NV_1^2| + |\V_0|. 
\end{aligned} .
\end{equation}

For $k \geq 2$, we have only new edges of types $(2,2)$ and $(2,3)$. If $\varepsilon \in \NE_{k-1}^{2,3}$, then there exists $\varepsilon' \in \NE_{k-1}^{2,3}$, such that $\tau_{\varepsilon}(\Delta) = \tau_{\varepsilon'}(\Delta)$. Thus, $\varepsilon$ 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, $\varepsilon$ will give origin to $p - 4 + 1$ edges in $\NE_{k}^{2,3}$, similarly to $\varepsilon'$, 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 $\varepsilon \in \NE_{k-1}^{2,2}$, then the reflection in $\varepsilon$ 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)$, $\varepsilon_1,\ldots,\varepsilon_{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,
\begin{equation}
\label{eq17}
\begin{aligned}
&|\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}|. 
\end{aligned}
\end{equation}

Equation $(\ref{eq13})$ provides the total amount.

\subsection{Counting the edges}

Subsections 3.1 and 3.2 provide recursive formulae for $\vert \NP_{k} \vert$ and $ \vert \NV_{k} \vert$, depending only on $\vert \NE_{k}^{j,l} \vert$. Thus, recursive formulae for $\vert \NE_{k}^{j,l} \vert$ 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$.


\begin{enumerate}
\item[i)] $p \geq 4$ and $q = 2m$. 
\end{enumerate}

Let $\varepsilon \in \NP_{k-1}$ be an external edge of $(k - 1)$-type $(2,j)$. We will assume that $j \leq q - 2$. The edge $\varepsilon$ is an edge of an external polygon $\Delta$, and, because $j \leq q - 2$, the reflected polygon $\Delta' = \rho_{\varepsilon}(\Delta)$ will have all but $\varepsilon$ as an external edge. That is, each $\varepsilon \in \cup_{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 $\varepsilon_1 \in \NE_{k-1}^{2,q}$, there is another edge $\varepsilon_2 \in \NE_{k-1}^{2,q}$, $\varepsilon_1 \neq \varepsilon_2$, such that $\tau(\varepsilon_1) = \tau(\varepsilon_2) = v$. For $i = 1,2$, let $\Delta_i \in \PP_{k-1}$ be such that $\varepsilon_i$ is an external edge of $\Delta_i$, and let $\varepsilon_i^*$ be another edge of $\Delta_i$ having $v$ as a vertex. Because $j = q$, $\varepsilon_2 \in \rho_{\varepsilon_1}(\Delta_1)$ and $\varepsilon_1 \in \rho_{\varepsilon_2}(\Delta_2)$, and actually $\rho_{\varepsilon_1}(\varepsilon_1^*) = \varepsilon_2$ and $\rho_{\varepsilon_2}(\varepsilon_2^*) = \varepsilon_1$, it follows that $\rho_{\varepsilon_1}(\Delta_1) = \rho_{\varepsilon_2}(\Delta_2)$. This is a new polygon having $p$ edges, except for $\varepsilon_1$ and $\varepsilon_2$, as external edges at level $k$. In short, for the case of $q = 2m$, 
\begin{eqnarray}
|\NE_k|& = & (p - 1) \sum_{j=2}^{q-2} |\NE_{k-1}^{2,j}| + \frac{(p-2)}{2} |\NE_{k-1}^{2,q}| \nonumber\\
&=&  (p - 1) \sum_{j=1}^{m-1} |\NE_{k-1}^{2,2j}| + \frac{(p-2)}{2} |\NE_{k-1}^{2,q}| \,. \label{eq18}
\end{eqnarray}

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 $\epsilon\in \E_{k-1}$ be a vertex of $(k-1)$-type $(2,j)$. Because $\varepsilon\in \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\leq j\leq q$.

If $\epsilon\in \NE_{k-2}^{2,2}$, it is the edge of a polygon $\Delta\in \PP_{k-2}$; considering the reflection $\rho_{\varepsilon}$ in the geodesic containing $\varepsilon$, $\rho_{\varepsilon}(\Delta)$ is a polygon containing $1$ edge
in $\E_{k-1}^{4,4}$ (actually this is the edge $\varepsilon$ itself), $2$ edges
in $\NE_{k-1}^{2,4}$ (those adjacent to $\varepsilon$), and all the other $(p-3)$ edges will be in $\NE_{k-1}^{2,2}$. Therefore, each $\varepsilon \in  \NE_{k-2}^{2,2}$ will generate
\begin{equation}
\label{chv1}
\begin{aligned}
&2 \,\, \text{edges} \in \NE_{k-1}^{2,4}, \\
&p - 3 \,\, \text{edges} \in \NE_{k-1}^{2,2}, \\
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,4}. 
\end{aligned}
\end{equation}

Now consider $\varepsilon\in \NE_{k-2}^{2,j}$, with $4 \leq j < q$. Because $q$ is even, we have $j<q-1$. Similar to the previous case,
$\varepsilon$ is an edge of a polygon $\Delta\in \PP_{k-2}$; considering the
reflection $\rho_{\varepsilon}$ in the geodesic containing $\varepsilon$,
$\rho_{\varepsilon}(\Delta)$ is a polygon containing $1$ edge
in $\E_{k-1}^{4,j+2}$ (actually, this is the edge $\varepsilon$ itself). The
edges of $\rho_{\varepsilon}(\Delta)$ adjacent to $\varepsilon$
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 $\rho_{\varepsilon}(\Delta)$ with no intersection with $\varepsilon$ will be vertices in $\NE_{k-1}^{2,2}$. In short, each $\varepsilon \in \E_{k-2}^{2,j}$ generates
\begin{equation}
\label{chv2}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,j+2}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,4}, \\
&p - 3 \,\, \text{edges} \in \NE_{k-1}^{2,2}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,j+2}. \end{aligned} 
\end{equation}

The case $j=q$ can occur only for an even $q$. In this case, there are two edges $\varepsilon$ and $\varepsilon^{\prime}$ of $(k-2)$ type $(2,q)$ joining a common vertex $v$ of type $q$. These are edges of distinct polygons $\Delta,\Delta^{\prime}\in \PP_{k-2}$; however, $\rho_{\varepsilon}(\Delta) = \rho_{\varepsilon^{\prime}}(\Delta^{\prime})$. We can see that
$\varepsilon$ and $\varepsilon^{\prime}$ become edges of type $(4,q)$, the other two distinct edges adjacent to $\varepsilon$ and
$\varepsilon^{\prime}$ become edges of $(k-1)$-type $(2,4)$, and the other $(p-4) $ edges of $\rho_{\varepsilon}(\Delta) = \rho_{\varepsilon^{\prime}}(\Delta^{\prime})$ are edges of type $(2,2)$. In short, each $\varepsilon \in \NE_{k-2}^{2,q}$ generates
\begin{equation}
\label{chv3}
\begin{aligned}
&\frac{1}{2} \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,q}, \\
&1 \,\, \text{edges} \in \NE_{k-1}^{2,4}, \\
&\frac{p - 4}{2} \,\, \text{edges} \in \NE_{k-1}^{2,2}. 
\end{aligned}
\end{equation}

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
\begin{equation}
\label{chv4}
f_{l}(j) = \begin{cases} 1, & \text{if $j \leq l - 1$;} \\
0 \, , & \text{if $j > l - 1$} \, ,
\end{cases}
\end{equation}
for $l, j \in \mathbb{Z}$ and $l \geq 1$. Then, we have the following:

\begin{theorem} \label{theorem5}Let $\{p,q\}$ be a tessellation with $p \geq 4$, $q = 2m$, $m \geq 2$, and $k \geq 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) \neq (2,2)$; $|\NE_1^{2,2}| = (p - 3) p$; and $|\NE_1^{2,4}| = 2 p$; $|\NE_1^{2,j}| = 0$ for $j > 4$. For the other levels,
\begin{align}
\vert \NE_{k-1}^{2,2} \vert  & =  (p- 3)  \vert \NE_{k-2}^{2,2} \vert +  (p-3) f_{m}(2) \sum_{j=2}^{m - 1} \vert \NE_{k-j}^{2,4} \vert + (p-4) \frac{ \vert \NE_{k-m}^{2,4} \vert}{2} \label{eq23} \\
\vert \NE_{k-1}^{2,4} \vert  & = 2  \vert \NE_{k-2}^{2,2} \vert
+ \sum_{j=2}^{m} \vert \NE_{k-j}^{2,4} \vert \label{eq24} \\
\vert \NE_{k-j}^{2,4} \vert & = 0 \,\, \mbox{for $k \leq j$} \nonumber \\
\vert \NE_{k - 1}^{2,2j} \vert  & =  \vert \NE_{k - (j - 1)}^{2,4} \vert \, \text{, for } \, 2 < j \leq m \, . \label{eq25}
\end{align}
The total at level $k$ is
\begin{align*}
|\NE_k| & = (p - 1)(p - 3 + 2 f_m(2))|\NE_{k-2}^{2,2}| + (p - 1) (f_{m}(2)(p - 2) + f_m(3)) \sum_{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}| \,.
\end{align*}
\end{theorem}

\begin{proof} 
Applying together the edges of the same type in $(\ref{chv1})$, $(\ref{chv2})$ and $(\ref{chv3})$, and because $q = 2m$, it follows that
\begin{align}
\vert \NE_{k-1}^{2,2} \vert  & = (p-3)  \sum_{j=2}%
^{q - 2} \vert \NE_{k-2}^{2,j} \vert + (p-4) \frac{ \vert \NE_{k-2}^{2,q} \vert}{2} = (p-3)  \sum_{j=1}%
^{m - 1} \vert \NE_{k-2}^{2,2j} \vert \nonumber \\
& + (p-4) \frac{ \vert \NE_{k-2}^{2,2m} \vert}{2} \label{eq26}\\
\vert \NE_{k-1}^{2,4} \vert  & = 2  \vert \NE_{k-2}^{2,2} \vert
+ \sum_{j=4}^{q-2} \vert \NE_{k-2}^{2,j} \vert + 2 \frac{ \vert \NE_{k-2}^{2,q} \vert}{2} = 2  \vert \NE_{k-2}^{2,2} \vert
+ \sum_{j=2}^{m} \vert \NE_{k-2}^{2,2j} \vert \label{eq27} \\
\vert \NE_{k-1}^{2,j+2} \vert  & =  \vert \NE_{k-2}^{2,j} \vert \text{, for } 4 \leq j \leq q-2 \label{eq28}
\end{align}

The relation $(\ref{eq28})$ is fundamental, and we obtain
\begin{equation}
\label{eq29}
	\vert \NE_{k-2}^{2,2j} \vert   =  \vert \NE_{k-j}^{2,4} \vert \, ,
\end{equation}
for $2 \leq j \leq m$. Applying $(\ref{eq29})$ in $(\ref{eq26})$ and $(\ref{eq27})$, we have
	\begin{align}
	\vert \NE_{k-1}^{2,2} \vert  & =  (p-3 )  \vert \NE_{k-2}^{2,2} \vert +  (p-3 ) \sum_{j=2}^{m - 1} \vert \NE_{k-j}^{2,4} \vert + (p-4) \frac{ \vert \NE_{k-m}^{2,4} \vert}{2} \label{eq30} \\
	\vert \NE_{k-1}^{2,4} \vert  & = 2  \vert \NE_{k-2}^{2,2} \vert
	+ \sum_{j=2}^{m} \vert \NE_{k-j}^{2,4} \vert \label{eq31}\\
	\vert \NE_{k - 1}^{2,2j} \vert  & =  \vert \NE_{k - (j - 1)}^{2,4} \vert \text{, for } 2 < j \leq m \, , \label{eq32}
	\end{align}

	where $ \vert \NE_{k-j}^{2,4} \vert = 0$ for $k \leq j$. The expression for $\vert \NE_{k-1}^{2,2}|$ in $(\ref{eq23})$ follows from $(\ref{eq31})$, 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 $(\ref{eq18})$
	\[
	|\NE_k| = (p - 1) \sum_{j=2}^{q-2} |\NE_{k-1}^{2,j}| + \frac{(p - 2)}{2} |\NE_{k-1}^{2,q}| = (p - 1) \sum_{j=1}^{m-1} |\NE_{k-1}^{2,2j}| + \frac{(p - 2)}{2} |\NE_{k-1}^{2,2m}|
	\]
	Now, using relations $(\ref{eq30})-(\ref{eq32})$, and considering the relation $\sum_{j=3}^{m-1} |\NE_{k-(j - 1)}^{2,4}| = \sum_{j=2}^{m-2} |\NE_{k-j}^{2,4}|$, the result follows .
\end{proof}

\begin{enumerate}
\item[ii)] $p \geq 4$ and $q = 2m + 1$. 
\end{enumerate}
In this case, we must be more careful. If $j = q - 1$, given an edge $\varepsilon_1 \in \NE_{k-1}^{2,q-1}$, there is another edge $\varepsilon_2 \in \NE_{k-1}^{2,q-1}$ joining a common vertex. Because (for $i = 1,2$) $\Delta_i$ is a polygon in $\PP_{k-1}$, such that $\varepsilon_i$ is an (exterior) edge of $\Delta_i$, we have $\varepsilon = \rho_{\varepsilon_1}(\Delta_1) \cap \rho_{\varepsilon_2}(\Delta_2)$, and thus each of the edges $\varepsilon_1$ and $\varepsilon_2$ contribute with $(p-2)$ new external edges at level $k$, in addition to $\varepsilon$. Now, $\varepsilon$ is also a new edge in $|\NE_k|$ and must also be computed. Because $\varepsilon_1$ and $\varepsilon_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$, 
\begin{equation}
\label{eq33}
|\NE_k| = (p-1) \sum_{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}| \, .
\end{equation}

Now, let $\varepsilon \in \NE_{k-2}^{2,j}$. The case $j=q$ can occur only for an even $q$, and thus $2 \leq j \leq q - 1$. For $j < q - 1$, we have the same reasoning as case $i)$, obtaining $(\ref{chv1})$ and $(\ref{chv2})$. 

For $j = q-1$, let $\varepsilon = \varepsilon_1, \varepsilon_2, \ldots,\varepsilon_{q-1}$ be the set of all $q-1$ edges with the common vertex $v = \tau(\varepsilon) \in \V_{k-2}$ numbered such that the angle between the consecutive edges is $2\pi/q$. Because $q-1 = 2m$, $\varepsilon_{q-1} \in \NE_{k-2}^{2,q-1}$. Let $\Delta \in \PP_{k-2}$ be the polygon containing $\varepsilon$; then, $\Delta_1 = \rho_{\varepsilon}(\Delta)$ and $\Delta_2 = \rho_{\varepsilon_{q-1}}(\cdots(\rho_{\varepsilon_2}(\Delta ))\cdots)$ have a common edge $\varepsilon'$ of type $ (3,q )$. The other distinct edge of $\Delta_1$ adjacent to $\varepsilon'$ is an edge of $(k-1)$-type $(3,q)$. The other $(p-4)$ edges of $\Delta_1$ are edges of type $(2,2)$. In short, $\varepsilon \in \NE_{k-2}^{2,q-1}$ generates
\begin{equation}
\label{chv5}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,q}, \\
&\frac{1}{2} \,\, \text{edges} \in \NE_{k-1}^{3,q}, \\
&1 \,\, \text{edges} \in \NE_{k-1}^{2,4}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,3}, \\
&p - 4 \,\, \text{edges} \in \NE_{k-1}^{2,2}.
\end{aligned}
\end{equation}

Now, we obtain the following result.

\begin{theorem} \label{theorem6}Let $\{p,q\}$ be a tessellation with $p \geq 4$, $q = 2m + 1$, $m \geq 2$ and $k \geq 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) \neq (2,2)$, $|\NE_1^{2,2}| = (p - 3) p$; $|\NE_1^{2,4}| = 2 p$, and $|\NE_1^{2,j}| = 0$ for $j > 4$; and for the other levels
	\begin{align}
	\vert \NE_{k-1}^{2,2} \vert  & = (p-3)  \vert \NE_{k-2}^{2,2} \vert
	+ (p-3) f_m(2) \sum_{j=2}^{m - 1}  \vert \NE_{k-j}^{2,4} \vert + (p-3) \sum_{j=1}^{m - 1}  \vert \NE_{k-(j+m)}^{2,4} \vert + \label{eq35} \\ \nonumber
	& + (p-4)  \vert \NE_{k-m}^{2,4} \vert \\
	\vert \NE_{k-1}^{2,4} \vert  & = 2  \vert \NE_{k-2}^{2,2} \vert + \sum_{j=1}^{m - 1}  \vert \NE_{k-(j+m)}^{2,4} \vert + \sum_{j=2}^{m}  \vert \NE_{k-j}^{2,4} \vert \label{eq36} \\
	\vert \NE_{k-1}^{2,2j}  \vert & =  \vert \NE_{k-(j - 1)}^{2,4} \vert \text{, for } 2 \leq j \leq m \label{eq37} \\
	\vert \NE_{k-1}^{2,2 j + 1}  \vert & =  \vert \NE_{k- (j + m - 1)}^{2,4} \vert \text{, for } 1 \leq j \leq m \label{eq38} \\
	\vert \NE_{k-1}^{2,3} \vert  & = \vert \NE_{k-m}^{2,4} \vert \label{eq39} \\
	\vert \NE_{k-1}^{3,q} \vert  & = \frac{ \vert \NE_{k-m}^{2,4} \vert}{2} \, , \label{eq40}
	\end{align}
	The total at level $k$ is
	\begin{align*}
	|\NE_k| & = (p - 1)(p - 3 + 2 f_m(2))|\NE_{k-2}^{2,2}| + (p - 1)^2 f_{m}(3) \sum_{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) \sum_{j=2}^{m - 1} |\NE_{k-(j + m - 1)}^{2,4}| \\
	& + (p^2 - 7 p/2 + 2 + f_m(2)(p - 1)) |\NE_{k-(2 m - 1)}^{2,4}\vert +  (p - 1)(p - 3 + f_m(2))|\NE_{k-m}^{2,4}|\,.
	\end{align*}
\end{theorem}

\begin{proof} 
	
Applying together the edges of the same type in $(\ref{chv1})$, $(\ref{chv2})$, $(\ref{chv5})$, and since because $q - 1 = 2m$, it follows that
\begin{align}
\vert \NE_{k-1}^{2,2} \vert  & = (p-3)  \sum_{j=2}%
^{q - 2} \vert \NE_{k-2}^{2,j} \vert + (p-4)  \vert \NE_{k-2}^{2,q-1} \vert \label{eq41}\\
\vert \NE_{k-1}^{2,4} \vert  & = 2  \vert \NE_{k-2}^{2,2} \vert
+ \sum_{j=3}^{q-1} \vert \NE_{k-2}^{2,j} \vert \label{eq42}\\
\vert \NE_{k-1}^{2,j+2} \vert  & =  \vert \NE_{k-2}^{2,j} \vert \text{, for } 3 \leq j \leq q-2 \label{eq43} \\
\vert \NE_{k-1}^{2,3} \vert  & = \vert \NE_{k-2}^{2,q-1} \vert \label{eq44} \\
\vert \NE_{k-1}^{3,q} \vert  & = \frac{ \vert \NE_{k-2}^{2,q-1} \vert}{2} \, , \label{eq45}
\end{align}
and $ \vert \NE_{k-1}^{2,3} \vert = \vert \NE_{k-1}^{3,q} \vert = 0$ for $k \leq \frac{q-3}{2}$.

In the equations $(\ref{eq41})$ and $(\ref{eq42})$, the term $|\NE_{k-2}^{2,j}|$ appears with even and odd $j$. When $(\ref{eq43})$ is used 
\begin{equation}
\label{eq46}
\vert \NE_{k-2}^{2,2j+1}  \vert =  \vert \NE_{k- (j + 1)}^{2,3} \vert \text{, for } 1 \leq j \leq m
\end{equation}
and
\begin{equation}
\label{47}
\vert \NE_{k-2}^{2,2j}  \vert =  \vert \NE_{k-j}^{2,4} \vert \text{, for } 2 \leq j \leq m \, .
\end{equation}

Because $q - 1 = 2m$, from $(\ref{eq44})$ and $(\ref{eq45})$,
\begin{equation}
\label{48}
\vert \NE_{k-1}^{2,3}  \vert = \vert \NE_{k-m}^{2,4} \vert \,.
\end{equation}
Now, from $(\ref{eq46})$, we obtain  $\vert \NE_{k - (j + 1)}^{2,3} \vert = \vert \NE_{k-(j + m)}^{2,4} \vert$, and applying together $(47)$,
\begin{equation}
\label{49}
\vert \NE_{k-2}^{2,2 j + 1} \vert = \vert \NE_{k- (j + m)}^{2,4} \vert \text{, for } 1 \leq j \leq m \, .
\end{equation}

Similarly, from $(\ref{eq45})$ and $(\ref{eq46})$,
\begin{equation}
\label{50}
\vert \NE_{k-1}^{3,q}  \vert = \frac{\vert \NE_{k-m}^{2,4} \vert}{2}\, .
\end{equation}

The expression for $\vert \NE_{k-1}^{2,2}|$ follows from $(\ref{eq41})$, 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 $(\ref{eq36}) - (\ref{eq40})$ in $(\ref{eq33})$, and through the same reasoning of Theorem \ref{theorem5}, the result follows .
\end{proof}
\begin{enumerate}
\item[iii)] $p \geq 6$ and $q = 3$. 
\end{enumerate}
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 $\varepsilon \in \NE_{k-1}^{2,3}$, $\varepsilon$ is an edge of a polygon $\Delta \in \PP_{k-1}$; there is another edge $\varepsilon' \in \NE_{k-1}^{2,3}$ in another polygon $\Delta' \in \PP_{k-1}$ with the same final vertex $v$ of $\varepsilon$. Considering the reflections $\rho_{\varepsilon}$ and $\rho_{\varepsilon'}$ on the geodesics containing $\varepsilon$ and $\varepsilon'$, respectively, then $\rho_{\varepsilon} (\Delta ) = \rho_{\varepsilon'} (\Delta' ) = \Delta''$.

Considering the polygon $\Delta$, because $\varepsilon \in \E_{k-1}^{2,3}$ and $p \geq 6$, there is a sequence of adjacent edges $\varepsilon = \varepsilon_1, \varepsilon_2, \cdots, \varepsilon_{p-3}$ such that $\varepsilon_{p-3} \in \E_{k-1}^{2,3}$ and $\varepsilon_2, \cdots, \varepsilon_{p-4} \in \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 $\varepsilon_{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 $\rho_{\varepsilon}(\Delta)$ will be vertices in $\E_{k}^{2,2}$. In short, each $\varepsilon \in \E_{k-1}^{2,3}$ generates
\begin{equation}
\label{eq51}
\begin{aligned}
&\frac{p-4}{2}  \,\, \text{edges} \in \E_{k}^{3,3}, \\
&1 \,\, \text{edge} \in \E_{k}^{2,3}, \\
&\frac{p - 6}{2} \,\, \text{edges} \in \E_{k}^{2,2}. 
\end{aligned}
\end{equation}

If $\varepsilon \in \NE_{k-1}^{2,2}$, $\varepsilon$ is an edge of a polygon $\Delta_1 \in \PP_{k-1}$. Let $\Delta_{1}'$ be its reflection in the geodesic containing $\varepsilon$, $\rho_{\varepsilon} (\Delta_1 ) = \Delta_{1}'$; $\Delta_{1}'$ then is a polygon containing $1$ edge in $\E_{k}^{3,3}$ (actually this is the edge $\varepsilon$ itself).
The edges of $\Delta_1'$, which are adjacent to $\varepsilon$, 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 $\rho_{\varepsilon} (  \Delta_1 )$ will be vertices in $\NE_{k}^{2,2}$. In short, each $\varepsilon \in \NE_{k-1}^{2,2}$ generates
\begin{equation}
\label{eq52}
\begin{aligned}
&2 \,\, \text{edges} \in \NE_{k}^{2,3}, \\
&p - 5 \,\, \text{edges} \in \NE_{k}^{2,2}. 
\end{aligned}
\end{equation}

Thus, putting together the edges of the same type in $(\ref{eq51})$ and $(\ref{eq52})$, it follows that

\begin{theorem} \label{theorem7}Let $\{p,3\}$ be a tessellation with $p \geq 6$ and $k \geq 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) \neq (2,2)$, $ \vert \NE_{1}^{2,2} \vert = p (p-5)$, $\vert \E_{1}^{2,3} \vert = 2p$ and $\vert \NE_{1}^{3,3} \vert = p$, and for the other levels,
	\begin{align}
	\vert \NE_{k}^{2,2} \vert  & = (p - 5)  \vert \NE_{k-1}^{2,2} \vert + \frac{p - 6}{2}  \vert \NE_{k-1}^{2,3} \vert \\
	\vert \NE_{k}^{2,3} \vert  & = 2  \vert \NE_{k-1}^{2,2} \vert
	+  \vert \NE_{k-1}^{2,3} \vert \\
	\vert \NE_{k}^{3,3} \vert  & = \frac{p - 4}{2} \vert \NE_{k-1}^{2,3} \vert \, ,
	\end{align}
	
	The total at level $k$ is
	\[
	|\NE_k| = (p - 3)|\NE_{k-1}^{2,2}| + (p - 4)|\NE_{k- 1}^{2,3}| \,.
	\]
\end{theorem}

Now, we turn to case $p = 3$. Then, $q \geq 6$, and there are no edges of type $(2,2)$ at levels $k > 1$. Let $\epsilon\in \E_{k-1}$ be an edge of $(k - 1)$-type $(2,j)$. Thus, $\varepsilon\in \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 \leq q$.
\begin{enumerate}
\item[iv)] $p = 3$, $q = 2m \geq 6$. 
\end{enumerate}
Consider $\varepsilon\in \NE_{k-2}^{2,j}$, with $4 \leq j < q$. Because $q$ is even, we have $j<q-1$. Now, $\varepsilon$ is an edge of a triangle $\Delta\in \NP_{k-2}$, and considering the reflection $\rho_{\varepsilon}$ in the geodesic containing $\varepsilon$, $\rho_{\varepsilon}(\Delta)$ is a triangle containing one edge in $\E_{k-1}^{4,j+2}$ (actually this is the edge $\varepsilon$ itself). The
two edges of $\rho_{\varepsilon}(\Delta)$ adjacent to $\varepsilon$
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 $\varepsilon \in \NE_{k-2}^{2,j}$ generates
\begin{equation}
\label{chv6}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,j+2}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,4}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,j+2}. 
\end{aligned}
\end{equation}
For $j=q$, there are two edges $\varepsilon$ and $\varepsilon^{\prime}$ of
$(k-2)$ type $(2,q)$ joining a common vertex $v$ of type $q$. These are edges of distinct polygons $\Delta,\Delta^{\prime} \in \PP_{k-2}$; however, $\rho_{\varepsilon}(\Delta)  = \rho_{\varepsilon^{\prime}}(\Delta^{\prime})$, and we can see that $\varepsilon$ and $\varepsilon^{\prime}$ become edges of type $(4,q)$. The triangle $\rho_{\varepsilon}(\Delta)$ will originate only one new edge, which is the same new edge as $\rho_{\varepsilon'}(\Delta)$. In short, each pair $\varepsilon$, $\varepsilon' \in \NE_{k-2}^{2,q}$ generates
\begin{equation}
\label{eq57}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,q}, \\
&1 \,\, \text{edge} = \varepsilon' \in \NE_{k-1}^{4,q}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{4,4}. 
\end{aligned}
\end{equation}
Now, if $\varepsilon \in \NE_{k-2}^{4,4}$, there exists $\Delta \in \PP_{k-2}$ with $\varepsilon \in \Delta$ such that $\rho_{\varepsilon}(\Delta)$ will originate two new edges of $\E_{k-1}^{2,6}$. 

Thus, we can prove the following result. 

\begin{theorem} \label{theorem8}Let $\{p,q\}$ be a tessellation with $p = 3$, $q = 2m$, $m \geq 2$ and $k \geq 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) \neq (2,2)$, $|\NE_1^{2,4}| = 2 p$; $|\NE_1^{2,j}| = 0$ for $j \neq 4$, and for the other levels
	\begin{align}
	\vert \NE_{k-1}^{2,4} \vert  & = \sum_{j=2}^{m-1} \vert \NE_{k-j}^{2,4} \vert \label{eq58}\\
	\vert \NE_{k - 1}^{2,2(j + 1)} \vert  & = \vert \NE_{k - j}^{2,4} \vert \text{, for } 2 \leq j \leq m-1 \label{eq59}\\
	\vert \NE_{k-1}^{4,4} \vert  & = \frac{1}{2}  \vert \NE_{k-2}^{2,q} \vert \label{eq60}\\
	\vert \NE_{k-1}^{2,6} \vert  & = 2  \vert \NE_{k-2}^{4,4} \vert  \label{eq61}\, ,
	\end{align}
	The total at level $k$ is
	\[
	|\NE_k| = 2(f_{m-1}(2) + f_{m}(3)) \sum_{j=2}^{m - 2} |\NE_{k-j}^{2,4}| + \frac{5}{2} |\NE_{k - m + 1}^{2,4}| + |\NE_{k-m}^{2,4}|  \,.
	\]
\end{theorem}

\begin{proof} 

Putting together the edges of the same type from $(\ref{chv6})$ and $(\ref{eq57})$, and because $q -2 = 2m -2 = 2 (m - 1)$, it follows that
\begin{align}
 \vert \NE_{k-1}^{2,4} \vert  & = \sum_{j=4}^{q-2} \vert \NE_{k-2}^{2,j} \vert = \sum_{j=2}^{m-1} \vert \NE_{k-2}^{2,2j} \vert \label{eq62}\\
 \vert \NE_{k-1}^{2,j+2} \vert  & = \vert \NE_{k-2}^{2,j} \vert \text{, for } 4 \leq j \leq q-2 \label{eq63}\\
 \vert \NE_{k-1}^{4,4} \vert  & = \frac{1}{2}  \vert \NE_{k-2}^{2,q} \vert \label{eq64}\\
 \vert \NE_{k-1}^{2,6} \vert  & = 2 \vert \NE_{k-2}^{4,4} \vert \label{eq65}
\end{align}
where $ \vert \NE_{k-j}^{2,4} \vert = 0$ for $k \leq j$. The relation $(\ref{eq63})$ is fundamental, and we obtain that
	\[
	\vert \NE_{k-2}^{2,2j} \vert  = \vert \NE_{k-j}^{2,4} \vert \, ,
	\]
	for $2 \leq j \leq m-1$. Applying this relation in $(\ref{eq62})$ and $(\ref{eq63})$, we have
	\begin{align}
	\vert \NE_{k-1}^{2,4} \vert  & = \sum_{j=2}^{m-1} \vert \NE_{k-j}^{2,4} \vert \label{eq66}\\
	\vert \NE_{k - 1}^{2,2(j + 1)} \vert  & =  \vert \NE_{k - j}^{2,4} \vert \text{, for } 2 \leq j \leq m-1 \label{eq67}\, .
	\end{align}
	We need a general formula for $|\NE_k|$, for $p = 3$. Let $\varepsilon \in \NP_{k-1}$ be an external edge of $(k - 1)$-type $(2,j)$. We assume that $j \leq q - 2$. The edge $\varepsilon$ is an edge of an external polygon $\Delta$, and, because $j \leq q - 2$, the reflected polygon $\Delta' = \rho_{\varepsilon}(\Delta)$ will have all but $\varepsilon$ as an external edge. That is, each $\varepsilon \in \cup_{j=1}^{q-2} \NE_{k-1}^{2,j}$ will give rise to $2$ new distinct edges in $\NE_k$. Given an edge $\varepsilon_1 \in \NE_{k-1}^{2,q}$, by $(\ref{eq64})$, $\varepsilon_1$ will give origin to $1/2$ of a new edge of $\NE_{k}^{4,4}$. Finally, given $\varepsilon_ 2 \in \NE_{k-1}^{4,4}$, by $(\ref{eq65})$, two new edges of $\NE_{k}^{2,6}$ will be originate . Therefore, we have
	\begin{equation}
	\label{eq68}
	|\NE_{k}| = 2 \sum_{j=2}^{m-1} |\NE_{k}^{2,2j}| + \frac{1}{2} |\NE_{k-1}^{2,2m}| + 2 |\NE_{k}^{4,4}| \,.
	\end{equation}
	Now, using $(\ref{eq68})$ and the relations $(\ref{eq64})-(\ref{eq67})$, the result follows .
\end{proof}
\begin{enumerate}
\item[v)] $p = 3$, $q = 2m + 1 \geq 7$. 
\end{enumerate}
Supposing for the moment that $4 \leq j \leq q - 2$, then $q > 4$, and each $\varepsilon \in \NE_{k-2}^{2,j}$ generates the same result as $(\ref{chv6})$.

For $j = q - 1$, let $\varepsilon = \varepsilon_1, \varepsilon_2, \ldots,\varepsilon_{q-1}$ be the set of all $q-1$ edges with the common vertex $v = \tau(\varepsilon)$, numbered such that the angles between the consecutive edges are $2\pi/q$. Because $q-1 = 2m$, $\varepsilon_{q-1} \in \E_{k-2}^{2,q-1}$. Let $\Delta \in \NP_{k-2}$ be the polygon containing $\varepsilon$; then, $\Delta_1 = \rho_{\varepsilon}(\Delta)$ and $\Delta_2 = \rho_{\varepsilon_{q-1}}(\cdots(\rho_{\varepsilon_2}(\Delta))\cdots)$ have a common edge $\varepsilon'$ of type $(3,q)$. The other distinct edge of $\Delta_1$ adjacent to $\varepsilon'$ is an edge of $(k-1)$-type $(3,4)$.

In short, each $\varepsilon \in \NE_{k-2}^{2,q-1}$ generates
\begin{equation}
\label{chv7}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,q}, \\
&\frac{1}{2} \,\, \text{edge} \in \NE_{k-1}^{3,q}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{3,4}. 
\end{aligned}
\end{equation}

The edges of $\NE_{k-1}^{3,q}$ will not contribute with new edges. For $\varepsilon \in \NE_{k-2}^{3,4}$, let $v^3_{k-2}$ be the initial vertex of $\varepsilon$, and let $\varepsilon'$ be the other edge of $\NE_{k-2}^{3,4}$, also with initial vertex in $v^3_{k-2}$. The reflection in $\varepsilon$ will originate a new edge of $\NE_{k-1}^{2,5}$, because we will have another new edge with a vertex in $v^3_{k-2}$, which will appear in the reflection in $\varepsilon'$, and a new edge of $\NE_{k-1}^{2,6}$. In short, each $\varepsilon \in \NE_{k-2}^{3,4}$ generates
\begin{equation}
\label{chv8}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{5,6}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,5}, \\
&1 \,\, \text{edge} \in \NE_{k-1}^{2,6}. 
\end{aligned}
\end{equation}

Now, for $j = q$, if $\varepsilon \in \NE_{k-2}^{2,q}$, let $\varepsilon = \varepsilon_1, \varepsilon_2,\ldots,\varepsilon_q$ be the set of edges with the same final vertex as $\varepsilon$. Because the angle between $\varepsilon_1$ and $\varepsilon_q$ is $2\pi/q$, the reflection in $\varepsilon$ will generate the same polygon as the reflection in $\varepsilon_q$. Thus, $\varepsilon$ will only generate
\begin{equation}
\label{chv9}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{4,q}, \\
&\frac{1}{2} \,\, \text{edge} \in \NE_{k-1}^{4,4}.
\end{aligned}
\end{equation}

Finally, if $\varepsilon \in \NE_{k-2}^{4,4}$, the reflection in $\varepsilon$ will generate two new edges, that is,
\begin{equation}
\label{chv10}
\begin{aligned}
&1 \,\, \text{edge} = \varepsilon \in \E_{k-1}^{6,6}, \\
&2 \,\, \text{edges} \in \NE_{k-1}^{2,6}.
\end{aligned}
\end{equation}

We can then prove the following result.

\begin{theorem} \label{theorem9}Let $\{p,q\}$ be a tessellation with $p = 3$, $q = 2m + 1$, $m \geq 2$ and $k \geq 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) \neq (2,2)$, $|\NE_1^{2,4}| = 2 p$, $|\NE_1^{2,j}| = 0$ for $j \neq 4$, and for the other levels
			\begin{align}
		\vert \NE_{k-1}^{2,4} \vert  & = \sum_{j=2}^{m-1} \vert \NE_{k-j}^{2,4} \vert + \sum_{j=2}^{m-1} \vert \NE_{k-j-1}^{3,4} \vert \label{eq73}\\
		\vert \NE_{k - 1}^{2,2j+1} \vert  & = \vert \NE_{k - (j - 1)}^{2,5} \vert \text{, for } 3 \leq j \leq m \label{74}\\
		\vert \NE_{k-1}^{3,q} \vert  & = \frac{1}{2}  \vert \NE_{k-2}^{2,q-1} \vert \label{75}\\
		\vert \NE_{k-1}^{3,4} \vert  & = \vert \NE_{k-2}^{2,q-1} \vert \label{eq76}\\
		\vert \NE_{k-1}^{4,4} \vert  & = \frac{1}{2}  \vert \NE_{k-j-2}^{3,4} \vert \label{eq77}\\
		\vert \NE_{k-1}^{2,6} \vert  & = 2  \vert \NE_{k-2}^{4,4} \vert + \vert \NE_{k-2}^{3,4} \vert \label{eq78}\\
		\vert \NE_{k-1}^{2,5} \vert  & = \vert \NE_{k-2}^{3,4} \vert \label{eq79}
		\end{align}
		where $\vert \NE_{k-j}^{2,4} \vert = \vert \NE_{k-j}^{2,5} \vert = 0$ for $k \leq j$.

The total at level $k$ is
	\begin{align*}
	|\NE_k| & = (2 + 2 f_m(3) + \frac{3}{2} f_{k-1}(m-2)f_4(m))|\NE_{k-2}^{2,4}| + 2 f_m(3)|\NE_{k-3}^{2,4}| + 4 f_m(4) \sum_{j=4}^{m - 2} |\NE_{k-j}^{2,4}| \\
	& + (4 f_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) \sum_{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}| \\
	& + 2 f_{k-1}(m-1) |\NE_{k-1}^{3,4}| + f_{k-1}(m+2) |\NE_{k-m-1}^{3,4}| \,.
	\end{align*}
\end{theorem}

\begin{proof} 
	Applying together the information of the edges of the same type from the relations $(\ref{chv6})$ and $(\ref{chv7})$ with $(\ref{chv10})$, and because $q - 3 = 2m + 1 - 3 = 2(m - 1)$, it follows that
	\begin{align}
	\vert \NE_{k-1}^{2,4} \vert  & = \sum_{j=4}^{q-2} \vert \NE_{k-2}^{2,j} \vert = \sum_{j=2}^{m-1} \vert \NE_{k-2}^{2,2j} \vert + \sum_{j=2}^{m-1} \vert \NE_{k-2}^{2,2j + 1} \vert \label{eq80}\\
	\vert \NE_{k-1}^{2,j+2} \vert  & = \vert \NE_{k-2}^{2,j} \vert \text{, for } 4 \leq j \leq q-2 \label{81}\\
	\vert \NE_{k-1}^{3,q} \vert  & = \frac{1}{2}  \vert \NE_{k-2}^{2,q-1} \vert \label{eq82}\\
	\vert \NE_{k-1}^{3,4} \vert  & = \vert \NE_{k-2}^{2,q-1} \vert \label{eq83}\\
	\vert \NE_{k-1}^{4,4} \vert  & = \frac{1}{2}  \vert \NE_{k-2}^{2,q} \vert \label{eq84}\\
	\vert \NE_{k-1}^{2,6} \vert  & = 2 \vert \NE_{k-2}^{4,4} \vert  \label{eq85}\\
	\vert \NE_{k-1}^{2,6} \vert  & = \vert \NE_{k-2}^{3,4} \vert  \label{eq86}\\
	\vert \NE_{k-1}^{2,5} \vert  & = \vert \NE_{k-2}^{3,4} \vert \label{eq87}
	\end{align}
	The relation $(81)$ is fundamental, and we obtain
	\begin{align}
	\vert \NE_{k-2}^{2,2j} \vert & = \vert \NE_{k-j}^{2,4} \vert \label{eq88}\\
	\vert \NE_{k-2}^{2,2j + 1} \vert & = \vert \NE_{k-j}^{2,5} \vert \label{eq89}\, ,
	\end{align}
	for $3 \leq j \leq m$. Combining $(\ref{eq89})$ with $(\ref{eq87})$ and $(\ref{eq84})$, we obtain the important relations
	\begin{align}
	\vert \NE_{k-2}^{2,2j + 1} \vert & = \vert \NE_{k-j - 1}^{3,4} \vert \text{, for } 2 \leq j \leq m \label{eq90}\\
	\vert \NE_{k-2}^{4,4} \vert & = \frac{1}{2} \vert \NE_{k-j - 2}^{3,4} \vert \label{91}\, .
	\end{align}
	Using these relations in $(\ref{eq80})-(\ref{eq87})$, we obtain the formulae $(\ref{eq73})-(\ref{eq79})$ in the theorem. 

	Because we are considering $k \geq 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 $(\ref{eq80})-(\ref{eq87})$, 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
	\[
	\vert \NE_{k-2}^{2,6} \vert = \vert \NE_{k-3}^{2,4} \vert + \frac{f_{k-2}(m+2)}{2} \vert \NE_{k-m-3}^{3,4} \vert + f_{k-2}(m-1) \vert \NE_{k-3}^{3,4} \vert \,.
	\]
	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 $\varepsilon \in \NP_{k-1}$ be an external edge of $(k - 1)$-type $(2,j)$. We assume that $j \leq q - 2$. The edge $\varepsilon$ is an edge of an external polygon $\Delta$. Because $j \leq q - 2$, the reflected polygon $\Delta' = \rho_{\varepsilon}(\Delta)$ will have all but $\varepsilon$ as an external edge. That is, $\varepsilon$ will give rise to $(p - 1) = 2$ distinct edges in $\NE_k$.
	
	If $j = q - 1$, given an edge $\varepsilon_1 \in \E_{k-1}^{2,q-1}$, there is another edge $\varepsilon_2 \in \E_{k-1}^{2,q-1}$ joining a common vertex. Considering (for $i = 1,2$) $\Delta_i$ as a polygon in $\PP_{k-1}$, such that $\varepsilon_i$ is an (exterior) edge of $\Delta_i$, we find that $\varepsilon = \rho_{\varepsilon_1}(\Delta_1) \cap \rho_{\varepsilon_2}(\Delta_2)$; thus, each of these edges $\varepsilon_1$ and $\varepsilon_2$ contribute along with $(p-2) = 1$ new external edges at level $k$, in addition to $\varepsilon$. Now, $\varepsilon$ is also a new edge of type $(3,q)$ in $|\NE_k|$, and the total number of edges must also be computed. Because $\varepsilon_1$ and $\varepsilon_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 $\varepsilon$ will contribute with $\frac{1}{2}$ new edge of type $(4,4)$. For $(i,j) = (3,4)$, let $\Delta$ be the polygon in $\NP_{k-1}$ such that $\varepsilon$ is an external edge. The reflection of $\varepsilon$ in $\Delta$ will give two new edges in $\E_k$.
	
	Finally, if $(i,j) = (4,4)$, the reflection in $\varepsilon$ will give origin to two new edges. Then, we have
	\begin{align}
	|\NE_k| & = 2 \sum_{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}|) \nonumber \\
	& + \frac{1}{2} f_{k-1}(2m-2) |\NE_{k-1}^{2,q}| + 2 f_{k-1}(m-1) |\NE_{k-1}^{3,4}| + 2 f_{k-1}(m + 2) |\NE_{k-1}^{4,4}| \label{eq92}\, .
	\end{align}
	
	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 $(\ref{eq92})$, we obtain the expression in the theorem.
	\end{proof}

\section{Acknowledgment}

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

\begin{thebibliography}{}

\bibitem{Albuquerque2009a}
C. D. Albuquerque, R. Palazzo Jr., and E. B. Silva,
Topological quantum codes on compact surfaces with genus $g\ge
2$, {\it J. Math. Phys.}, {\bf 50} (2009), 023513.

\bibitem{bartholdi}
L. Bartholdi and T. G. Ceccherini-Silberstein, Growth series and random walks on some hyperbolic graphs,
{\it Monatsh. Math.}, {\bf 136} (2002), 181--202.

\bibitem{Be}
A. F. Beardon, {\it The Geometry of Discrete Groups},  Springer, 1983.

\bibitem{Ca1}
J. W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, {\it Geom. Dedicata}, {\bf 16} (1984), 123--148.

\bibitem{Ca2}
J. W. Cannon and P. Wagreich, Growth functions of surface groups, {\it Math. Ann.}, {\bf 293} (1992), 239--257. 

\bibitem{Floyd}
W. J. Floyd and S. P. Plotnick, Growth functions for semi-regular tilings of the hyperbolic plane, {\it Geom. Dedicata}, {\bf 53} (1994), 1--23.

\bibitem{harpe}
R. Grigorchuk and P. De La Harpe, On problems related to growth, entropy, and spectrum in group theory, {\it J. Dyn. Control Syst.}, {\bf 3} (1997), 51--89.

\bibitem{Hu}
J. E. Humphreys, {\it Reflection Groups and Coxeter Groups}, Cambridge, 1990.

\bibitem{BFP}
E. B. Silva, M. Firer, and R. Palazzo Jr., Counting domains in $\{p,q\}$ tessellations, {\it Appl. Math. Lett.}, {\bf 16} (2003), 323--328.

\bibitem{Brandani2006}
E. B. Silva, S. R. Costa, M. Firer, and R. Palazzo Jr., Signal constellations in the hyperbolic plane: A proposal for new communication systems, {\it J. Franklin Inst.}, {\bf 343} (2006), 69--82.

\bibitem{Sullivan}
D. Sullivan, The density at infinity of a discrete group of hyperbolic motions, {\it Publ. Math. Inst. Hautes Etudes Sci.}, {\bf 50} (1979), 171--202.

\bibitem{Ungerboeck1987}
G. Ungerboeck, Trellis-coded modulation with redundant signal sets
part I: introduction, {\it IEEE Comm. Magazine}, {\bf 2} (1987), 5--11.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05B45, 52C20.

\noindent \emph{Keywords: } 
hyperbolic geometry, tiling, enumeration, counting edges, polygon.


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 26 2016;
revised versions received August 7 2017; September 9 2017;
November 18 2017.
Published in {\it Journal of Integer Sequences},
November 19 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.