Enumeration of rooted biloopless nonseparable planar near-triangulations

Long, Shude; Cai, Junliang

doi:10.61091/ars162-08

Abstract

1. Introduction
2. Functional equations
3. Enumeration
Acknowledgements
Conflict of interest

References

Ars Combinatoria

Volume 162
Pages: 93-102

Research article

Enumeration of rooted biloopless nonseparable planar near-triangulations

^¹, ^²

¹Department of Mathematics, Chongqing University of Arts and Sciences, Chongqing, 402160, P.R.China

²School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P.R.China

Accepted: 30/06/2024
Published Online: 22/03/2025

Copyright Link
License

Abstract

This paper investigates the number of rooted biloopless nonseparable planar near-triangulations and presents some formulae for such maps with three parameters: the valency of root-face, the number of edges and the number of inner faces. All of them are almost summation-free.

Keywords: map, triangulation, enumerating function, functional equation, Lagrangian inversion

1. Introduction

Throughout this paper we consider the rooted maps on the plane. Definitions of terms not given here may be found in [14]. The concept of a rooted map was first introduced by W.T. Tutte. His series of census papers [21,22,21] laid the foundation for the theory. Since then, the theory has been developed by many scholars such as Arqu‘es [1], Brown [4], Mullin [19,20], authors [2,3], Liskovets [10,11], authors [16,15], Walsh et al. [23], Mednykh & Nedela [17,18], Chapay & Dolega [7], Gao [8,9], Liu [12,13,14] and Cai & Liu [5,6]. In this article we deal with the enumerative problem of biloopless nonseparable planar near-triangulations with the valency of root-vertex, the valency of root-face, the number of edges and the number of inner faces as parameters.

A map is a connected graph cellularly embedded on a surface. A map $M$ is said to be rooted if an edge is distinguished as the root-edge and given a direction and one its two sides is also distinguished as the right-hand side. We denote the root-edge of $M$ by $e_{r} (M)$ and its tail vertex is chosen to be the root-vertex of this map, the face on the right-hand side of the root-edge is called the root-face. Without loss of generality, the root-face may be chosen as the infinite face. An isthmus of a map $M$ is such an edge belonging only one face in map $M$ . A map is called biloopless if there are no loops in the map and also in its dual map, i.e., there are no loops and no isthmuses in this map. A near-triangulation on a surface is a map on the surface such that each face possibly the root-face has valency three. A triangulation is a near-triangulation with root-face valency also bing three. A near-triangulation is said to be 2-boundary if its root-face valency is two.

A map is always denoted by $M = (X, P)$ , where $X = \sum_{x \in X} K x, K x = {x, α x, β x, α β x}, K$ is the Klein group of four elements denoted by $1, α, β, α β, X$ is a finite set and $P$ is a basic permutation on $X$ (A permutation $P$ on $X$ is said to be basic if for any $x \in X$ there does not exist an integer $k$ such that $P^{k} x = α x$ ).

For the power series $f (x), f (x, y)$ and $f (x, y, z)$ , we use the following notations:

$\partial_{x}^{m} f (x)$ , $\partial_{(x, y)}^{(m, l)} f (x, y),$ and $\partial_{(x, y, z)}^{(m, l, n)} f (x, y, z),$

to represent the coefficients of $x^{m}$ in $f (x)$ , $x^{m} y^{l}$ in $f (x, y)$ and $x^{m} y^{l} z^{n}$ in $f (x, y, z)$ , respectively.

In what follows we will enumerate rooted biloopless nonseparable planar near-triangulations. Several explicit expressions of its enumerating functions will be derived. And all of them are summations-free.

2. Functional equations

In this section we will set up the functional equations satisfied by the enumerating functions for rooted biloopless nonseparable planar near-triangulations.

We first introduce some operations on the maps in $M$ . For any map $M \in M$ , let $M - e_{r} (M)$ and $M ∙ e_{r} (M)$ be the maps obtained by deleting $e_{r} (M)$ , the root-edge, from $M$ and contracting $e_{r} (M)$ into a vertex as the new root-vertex, respectively.

Given two maps $M_{1}$ and $M_{2}$ with roots $r_{1} = r (M_{1})$ and $r_{2} = r (M_{2})$ , respectively. We define $M = M_{1} \hat{+} M_{2}$ to be the map obtained by identifying the vertex $v_{(P α β) r_{1}}$ of $M_{1}$ and the root-vertex $v_{r_{2}}$ of $M_{2}$ , the root-edge of $M$ is the same as those of $M_{1}$ , but the root-face of $M$ is the composition of the root-faces of $M_{1}$ and $M_{2}$ . Further, for two sets of maps $M_{1}$ and $M_{2}$ , the set of maps $M_{1} \hat{⊙} M_{2} = {M_{1} \hat{+} M_{2} | M_{i} \in M_{i}, i = 1, 2}$ .

Let $T$ be the set of all rooted biloopless nonseparable planar near-triangulations. Suppose that its enumerating function is $\begin{aligned} f_{T} (x, y, z, w) = \sum_{M \in T} x^{m (M)} y^{l (M)} z^{n (M)} w^{s (M)}, \end{aligned}$ where $m (M), l (M), n (M)$ and $s (M)$ are, respectively, the root-vertex valency, the root-face valency, the number of edges and the number of inner faces of $M$ . Moreover, we write that $\begin{aligned} g_{T} (y, z, w) = f_{T} (1, y, z, w), h_{T} (y, w) = g_{T} (y, 1, w) = f_{T} (1, y, 1, w) . \end{aligned}$

The family $T$ may be partitioned into three parts as $\begin{matrix} (1) & \begin{aligned} T = T_{1} + T_{2} + T_{3}, \end{aligned} \end{matrix}$ where $T_{1}$ consists of only the triangle and $T_{2} = {M | M \in T, M - e_{r} (M) \in T}$ .

Further, $T_{3}$ is divided into two parts as follows: $\begin{matrix} (2) & \begin{aligned} T_{3} = T_{31} + T_{32}, \end{aligned} \end{matrix}$ where $T_{31} = {M | M \in T, M - e_{r} (M)$ has an isthmus $}$ .

Lemma 2.1. Let $T_{< 2 >} = {M - e_{r} (M) | M \in T_{2}}$ . Then, $\begin{matrix} (3) & \begin{aligned} T_{< 2 >} = T - T (2), \end{aligned} \end{matrix}$ where $T (2)$ is the set of all rooted 2-boundary biloopless nonseparable planar near-triangulations.

Proof. For any map $M^{'} \in T_{< 2 >}$ , there is a map $M \in T_{2}$ such that $M^{'} = M - e_{r} (M)$ . It is obvious that the valency of the root-face of $M^{'}$ ia at least three. It implies that $M^{'}$ is a member of the set of right hand side in (3). On the other hand, for any map $M^{'} \in T - T (2)$ , one may yield a map $M$ by adding a new edge from the root-vertex $v_{r^{'}}$ of $M^{'}$ to the vertex $v_{(P α β)^{2} r^{'}}$ of $M^{'}$ ; the new edge is the root-edge of $M$ , and $M \in T_{2}$ .

If map has a single edge, and the edge is not a loop, then it is called the link map denoted by $L$ . We now have the following:

Lemma 2.2. Let $T_{< 31 >} = {M - e_{r} (M) | M \in T_{31}}$ . Then, $\begin{matrix} (4) & \begin{aligned} T_{< 31 >} = L \hat{⊙} T + T \hat{⊙} L . \end{aligned} \end{matrix}$

Proof. For any map $M^{'} \in T_{< 31 >}$ , there exists a map $M \in T$ such that $M^{'} = M - e_{r} (M)$ has an isthmus. If the isthmus is the root-edge of $M^{'}$ , $M^{'} \in L \hat{⊙} T$ ; Otherwise, $M^{'} \in T \hat{⊙} L$ . Conversely, for any map $M^{'} = L \hat{+} M^{″}$ (or $M^{'} = M^{″} \hat{+} L$ ), where $M^{″} \in T$ , one may obtain a map $M$ by adding a new edge from the root-vertex $v_{r^{'}}$ of $M^{'}$ to the vertex $v_{(P α β)^{2} r^{'}}$ of $M^{'}$ ; the new edge is the root-edge of $M$ . Obviously, $M \in T_{31}$ .

Lemma 2.3. Let $T_{< 32 >} = {M - e_{r} (M) | M \in T_{32}}$ . Then, $\begin{matrix} (5) & \begin{aligned} T_{< 32 >} = T \hat{⊙} T . \end{aligned} \end{matrix}$

Proof. For any $M^{'} \in T_{< 32 >}$ , where $M^{'} = M - e_{r} (M), M \in T_{32}$ . Since $M^{'}$ has no isthmus and $M^{'}$ is separable, it has a cut-vertex. This implies that $M^{'} \in T \hat{⊙} T$ . On the other hand, for any $M^{'} = M_{1} \hat{+} M_{2} (M_{i} \in T, i = 1, 2)$ , one may yield a map $M$ by adding a new edge from the root-vertex $v_{r_{1}}$ of $M_{1}$ to the vertex $v_{β r_{2}}$ of $M_{2}$ ; the new edge is the root-edge of $M$ , and $M \in T_{32}$ .

We now present the first main result.

Theorem 2.4. The enumerating function $f = f_{T} (x, y, z, w)$ satisfies the following equation: $\begin{matrix} (6) & \begin{aligned} (y - x z w - x y^{2} z^{2} w - x z w g) f = x^{2} y^{4} z^{3} w + x^{2} y^{2} z^{2} w g - x y^{2} z w F_{2}, \end{aligned} \end{matrix}$ where $g = f_{T} (1, y, z, w)$ and $F_{2} = F_{2} (x, z, w)$ is the coefficient of $y^{2}$ in $f$ .

Proof. Let $f_{T_{i}}$ be the enumerating function of $T_{i}$ . We are now going to evaluate the contribution $f_{T_{i}}$ of $T_{i}$ to $f (i = 1, 2, 3)$ .

It is clear that $\begin{aligned} f_{T_{1}} = x^{2} y^{3} z^{3} w . \end{aligned}$

By Lemma 2.1, we have $\begin{aligned} f_{T_{2}} = x y^{- 1} z w \sum_{M \in T - T (2)} x^{m (M)} y^{l (M)} z^{n (M)} w^{s (M)} = x y^{- 1} z w (f - y^{2} F_{2}), \end{aligned}$ where $F_{2} = F_{2} (x, z, w)$ is the coefficient of $y^{2}$ in $f$ .

By Lemma 2.2, we have $\begin{aligned} f_{T_{31}} = & x^{2} y z^{2} w \sum_{M \in T} y^{l (M)} z^{n (M)} w^{s (M)} + x y z^{2} w \sum_{M \in T} x^{m (M)} y^{l (M)} z^{n (M)} w^{s (M)} \\ = & x^{2} y z^{2} w g + x y z^{2} w f, \end{aligned}$ where $g = g_{T} (y, z, w) = f_{T} (1, y, z, w)$ .

By Lemma 2.3, we have $\begin{aligned} f_{T_{32}} = & x y^{- 1} z w (\sum_{M_{1} \in T} x^{m (M_{1})} y^{l (M_{1})} z^{n (M_{1})} w^{s (M_{1})}) (\sum_{M_{2} \in T} y^{l (M_{2})} z^{n (M_{2})} w^{s (M_{2})}) \\ = & x y^{- 1} z w f g, \end{aligned}$ where $g = g_{T} (y, z, w) = f_{T} (1, y, z, w)$ .

Thus, $\begin{aligned} f_{T_{3}} = & f_{T_{31}} + f_{T_{32}} = x^{2} y z^{2} w g + x y z^{2} w f + x y^{- 1} z w f g . \end{aligned}$

Since $f = f_{T_{1}} + f_{T_{2}} + f_{T_{3}}$ , the theorem can be obtained soon.

If $x = 1$ , then we have:

Corollary 2.5. The enumerating function $g = g_{T} (y, z, w)$ satisfies the following equation: $\begin{matrix} (7) & \begin{aligned} z w g^{2} + (2 y^{2} z^{2} w + z w - y) g + y^{4} z^{3} w - y^{2} z w G_{2} = 0, \end{aligned} \end{matrix}$ where $G_{2} = G_{2} (z, w) = F_{2} (1, z, w)$ is the coefficient of $y^{2}$ in $g$ .

Let $z = 1$ in (7). Then we get

Corollary 2.6. The enumerating function $h = h_{T} (y, w)$ satisfies the following equation: $\begin{matrix} (8) & \begin{aligned} w h^{2} + (2 y^{2} w + w - y) h + y^{4} w - y^{2} w H_{2} = 0, \end{aligned} \end{matrix}$ where $H_{2} = H_{2} (w) = G_{2} (1, w) = F_{2} (1, 1, w)$ is the coefficient of $y^{2}$ in $h$ .

3. Enumeration

In this section we concentrate on finding the explicit formulae for enumerating functions $g = g_{T} (y, z, w)$ and $h = h_{T} (y, w)$ by using Lagrangian inversion [24] here.

The discriminant of Eq. (7) is $\begin{matrix} (9) & \begin{aligned} δ (y, z, w) = & (2 y^{2} z^{2} w + z w - y)^{2} - 4 z w (y^{4} z^{3} w - y^{2} z w G_{2}) \\ = & z^{2} w^{2} - 2 z w y + (1 + 4 z^{3} w^{2} + 4 z^{2} w^{2} G_{2}) y^{2} - 4 z^{2} w y^{3} . \end{aligned} \end{matrix}$

Although (9) is not necessarily to be a perfect square, we may assume that $\begin{matrix} (10) & \begin{aligned} δ (y, z, w) & = (z w - a y)^{2} (1 - 2 b y) \\ = z^{2} w^{2} - 2 z w (a + b z w) y + (a^{2} + 4 a b z w) y^{2} - 2 a^{2} b y^{3}, \end{aligned} \end{matrix}$ in which $a$ and $b$ are functions of $y, z$ and $w$ .

By identifying the coefficients of $y^{i}$ in (9) and (10), one may find the parametric expressions as follows: $\begin{matrix} (11) & {\begin{cases} a + b z w = 1, \\ a^{2} b = 2 z^{2} w, \\ a^{2} + 4 a b z w = 1 + 4 z^{3} w^{2} + 4 z^{2} w^{2} G_{2} . \end{cases} \end{matrix}$

If introducing the parameter $η$ such that $b z w = 2 η$ , one may follow from (11) that $\begin{matrix} (12) & {\begin{cases} a = 1 - 2 η, \\ b z w = 2 η, \\ z^{3} w^{2} = η (1 - 2 η)^{2}, \\ z^{2} w^{2} (G_{2} + z) = η (1 - 3 η) . \end{cases} \end{matrix}$

By (12) we obtain the following parametric expressions of function $G_{2} = G_{2} (z, w)$ : $\begin{matrix} (13) & \begin{aligned} {\begin{cases} z^{3} w^{2} = η (1 - 2 η)^{2}, \\ z^{2} w^{2} (G_{2} + z) = η (1 - 3 η) . \end{cases} \end{aligned} \end{matrix}$

Theorem 3.1. The coefficient of $y^{2}$ in $f_{T} (y, z, w)$ is $\begin{matrix} (14) & \begin{aligned} G_{2} = & \sum_{n \geq 1} \frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!} z^{3 n + 1} w^{2 n} . \end{aligned} \end{matrix}$

Proof. Applying Lagrangian inversion [24] to (13), we have $\begin{aligned} G_{2} + z = & \sum_{n \geq 1} {\frac{z^{3 n - 2} w^{2 n - 2}}{n!} \frac{d^{n - 1}}{d η^{n - 1}} [\frac{1 - 6 η}{(1 - 2 η)^{2 n}}] |}_{η = 0} \\ = & \sum_{n \geq 1} \frac{2^{n - 1}}{n} [(\binom{3 n - 2}{n - 1}) - 3 (\binom{3 n - 3}{n - 2})] z^{3 n - 2} w^{2 n - 2} \\ = & \sum_{n \geq 1} \frac{2^{n - 1} (3 n - 3)!}{n! (2 n - 1)!} z^{3 n - 2} w^{2 n - 2} \\ = & \sum_{n \geq 0} \frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!} z^{3 n + 1} w^{2 n}, \end{aligned}$ and it implies that $\begin{aligned} G_{2} = & \sum_{n \geq 1} \frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!} z^{3 n + 1} w^{2 n}, \end{aligned}$ as desired.

Let $z = 1$ in (14). Then we yield

Corollary 3.2. The coefficient of $y^{2}$ in $h_{T} (y, w)$ is $\begin{matrix} (15) & \begin{aligned} H_{2} = & \sum_{n \geq 1} \frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!} w^{2 n} . \end{aligned} \end{matrix}$

As a consequence of Theorem 3.1, the number of rooted 2-boundary biloopless separable planar near-triangulation with $2 n$ inner faces (or $3 n + 1$ edges) is $\frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!},$ for $n \geq 1$ . It is easy to see that there exists a 1-1 correspondence between the sets of all rooted 2-boundary biloopless nonseparable planar near-triangulations and all rooted biloopless nonseparable planar triangulations. Thus, we have the following

Corollary 3.3. The number of rooted biloopless nonseparable planar triangulations with $2 n - 1$ inner faces (or $3 n$ edges) is $\begin{matrix} (16) & \begin{aligned} \frac{2^{n + 1} (3 n)!}{n! (2 n + 2)!}, \end{aligned} \end{matrix}$ for $n \geq 1$ .

Now, let $1 - 2 b y = α^{2}$ , then by (10), (12) and Eq. (7), we have $\begin{matrix} (17) & \begin{aligned} g = \frac{y - z w - 2 y^{2} z^{2} w + (z w - a y) α}{2 z w} . \end{aligned} \end{matrix}$

Furthermore, let $α = \frac{1 - ξ η}{1 + ξ η}$ . By (12) and (17), one may find the following parametric expression of the function $g = g_{T} (y, z, w)$ : $\begin{matrix} (18) & \begin{aligned} {\begin{cases} z^{- 1} w^{- 1} y = \frac{ξ}{(1 + ξ η)^{2}}, \\ z^{3} w^{2} = η (1 - 2 η)^{2}, \\ g = \frac{ξ^{2} η^{2} (1 - 2 η) (2 + ξ)}{(1 + ξ η)^{4}} - \frac{ξ^{2} η^{2}}{(1 + ξ η)^{2}} . \end{cases} \end{aligned} \end{matrix}$

By (18) we have $\begin{matrix} (19) & Δ_{(ξ, η)} = | \begin{matrix} \frac{1 - ξ η}{1 + ξ η} & * \\ 0 & \frac{1 - 6 η}{1 - 2 η} \end{matrix} | = \frac{(1 - ξ η) (1 - 6 η)}{(1 + ξ η) (1 - 2 η)} . \end{matrix}$

Theorem 3.4. The enumerating function $g = g_{T} (y, z, w)$ has the following explicit expression: $\begin{matrix} (20) & \begin{aligned} g_{T} (y, z, w) = & \sum_{s \geq 1} \sum_{n = ⌈ \frac{3 s + 2}{2} ⌉}^{2 s + 1} \frac{2^{2 s - n + 1} (4 n - 6 s - 2)!}{(2 n - 3 s - 2)! (2 n - 3 s - 1)! (2 s - n + 1)!} \frac{(n - 1)!}{(2 n - 2 s)!} y^{2 n - 3 s} z^{n} w^{s} . \end{aligned} \end{matrix}$

Proof. By employing Lagrangian inversion with two parameters [24], from (18) and (19) one may find that $\begin{aligned} g_{T} (y, z, w) = & \sum_{l \geq 0} \sum_{s \geq 0} \partial_{(ξ, η)}^{(l, s)} \frac{(1 + ξ η)^{2 l - 1} (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s + 1}} \\ \times [\frac{ξ^{2} η^{2} (1 - 2 η) (2 + ξ)}{(1 + ξ η)^{4}} - \frac{ξ^{2} η^{2}}{(1 + ξ η)^{2}}] y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{l \geq 2} \sum_{s \geq 2} [\partial_{(ξ, η)}^{(l - 2, s - 2)} \frac{(1 + ξ η)^{2 l - 5} (2 + ξ) (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s}} \\ - \partial_{(ξ, η)}^{(l - 2, s - 2)} \frac{(1 + ξ η)^{2 l - 3} (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s + 1}}] y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 2} [\sum_{l \geq 2} 2 \partial_{(ξ, η)}^{(l - 2, s - 2)} \frac{(1 + ξ η)^{2 l - 5} (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s}} \\ + \sum_{l \geq 3} \partial_{(ξ, η)}^{(l - 3, s - 2)} \frac{(1 + ξ η)^{2 l - 5} (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s}} \\ - \sum_{l \geq 2} \partial_{(ξ, η)}^{(l - 2, s - 2)} \frac{(1 + ξ η)^{2 l - 3} (1 - ξ η) (1 - 6 η)}{(1 - 2 η)^{2 s + 1}}] y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 2} {\sum_{l = 2}^{s} 2 [(\binom{2 l - 5}{l - 2}) - (\binom{2 l - 5}{l - 3})] \partial_{η}^{s - l} \frac{1 - 6 η}{(1 - 2 η)^{2 s}} \\ + \sum_{l = 3}^{s + 1} [(\binom{2 l - 5}{l - 3}) - (\binom{2 l - 5}{l - 4})] \partial_{η}^{s - l + 1} \frac{1 - 6 η}{(1 - 2 η)^{2 s}} \\ - \sum_{l = 2}^{s} [(\binom{2 l - 3}{l - 2}) - (\binom{2 l - 3}{l - 3})] \partial_{η}^{s - l} \frac{1 - 6 η}{(1 - 2 η)^{2 s + 1}}} y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 2} \frac{2^{s} (3 s - 3)!}{(s - 1)! (2 s)!} y^{2} z^{3 s - 2} w^{2 s - 2} + \sum_{s \geq 2} [\sum_{l = 3}^{s + 1} \frac{(2 l - 5)! 2}{(l - 3)! (l - 1)!} \partial_{η}^{s - l + 1} \frac{1 - 6 η}{(1 - 2 η)^{2 s}} \\ - \sum_{l = 3}^{s} \frac{(2 l - 3)! 2}{(l - 2)! l!} \partial_{η}^{s - l} \frac{1 - 6 η}{(1 - 2 η)^{2 s + 1}}] y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 2} \frac{2^{s} (3 s - 3)!}{(s - 1)! (2 s)!} y^{2} z^{3 s - 2} w^{2 s - 2} \\ + \sum_{s \geq 2} \sum_{l = 3}^{s + 1} \frac{2^{s - l + 1} (2 l - 2)! (3 s - l - 1)!}{(l - 2)! (l - 1)! (s - l + 1)! (2 s)!} y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 2} \sum_{l = 2}^{s + 1} \frac{2^{s - l + 1} (2 l - 2)! (3 s - l - 1)!}{(l - 2)! (l - 1)! (s - l + 1)! (2 s)!} y^{l} z^{3 s - l} w^{2 s - l} \\ = & \sum_{s \geq 1} \sum_{n = ⌈ \frac{3 s + 2}{2} ⌉}^{2 s + 1} \frac{2^{2 s - n + 1} (4 n - 6 s - 2)! (n - 1)!}{(2 n - 3 s - 2)! (2 n - 3 s - 1)! (2 s - n + 1)! (2 n - 2 s)!} y^{2 n - 3 s} z^{n} w^{s} . \end{aligned}$ This completes the proof of Theorem 3.4.

The first few terms of $g = g_{T} (y, z, w)$ are as follows: $\begin{aligned} g_{T} (x, y, z, v) = y^{3} z^{3} w + y^{2} z^{4} w^{2} + 2 y^{4} z^{5} w^{2} + 4 y^{3} z^{6} w^{3} + 5 y^{5} z^{7} w^{3} + \dots . \end{aligned}$

Finally, we give several useful corollaries of Theorem 3.4.

Corollary 3.5. The enumerating function $h = h_{T} (y, w)$ has the following explicit expression: $\begin{matrix} (21) & \begin{aligned} h_{T} (y, w) = & \sum_{s \geq 1} \sum_{l = ⌈ \frac{s + 2}{2} ⌉}^{s + 1} \frac{2^{s - l + 1} (4 l - 2 s - 2)! (l + s - 1)!}{(2 l - s - 2)! (2 l - s - 1)! (s - l + 1)! (2 l)!} y^{2 l - s} w^{s} . \end{aligned} \end{matrix}$

Proof. It follows easily from (20) by taking $z = 1$ and $n = l + s$ .

Corollary 3.6. The number of rooted biloopless nonseparable planar near-triangulations with $n$ edges and $s$ inner faces is $\begin{matrix} (22) & \frac{2^{2 s - n + 1} (4 n - 6 s - 2)! (n - 1)!}{(2 n - 3 s - 2)! (2 n - 3 s - 1)! (2 s - n + 1)! (2 n - 2 s)!}, \end{matrix}$ for $s \geq 1$ and $⌈ \frac{3 s + 2}{2} ⌉ \leq n \leq 2 s + 1$ .

Proof. It follows immediately from (20) with $y = 1$ .

Corollary 3.7. The number of rooted biloopless nonseparable planar near-triangulations with $n$ edges is $\begin{matrix} (23) & \begin{aligned} \sum_{i = ⌈ \frac{n + 2}{3} ⌉}^{⌊ \frac{n + 1}{2} ⌋} \frac{2^{n - 2 i + 1} (6 i - 2 n - 2)! (n - 1)!}{(3 i - n - 2)! (3 i - n - 1)! (n - 2 i + 1)! (2 i)!}, \end{aligned} \end{matrix}$ for $n \geq 3$ .

Proof. It follows easily from (20) by putting $y = w = 1$ and $s = n - i$ .

Corollary 3.8. The number of rooted biloopless nonseparable planar near-triangulations with $s$ inner faces is $\begin{matrix} (24) & \begin{aligned} \sum_{i = ⌈ \frac{s + 2}{2} ⌉}^{s + 1} \frac{2^{s - i + 1} (4 i - 2 s - 2)! (s + i - 1)!}{(2 i - s - 2)! (2 i - s - 1)! (s - i + 1)! (2 i)!}, \end{aligned} \end{matrix}$ for $s \geq 1$ .

Proof. It follows immediately from (21) with $y = 1$ and $l = i$ .

Acknowledgements

Supported by the NNSFC under Grant No. 10271017, Chongqing Municipal Education Commission under Grant No. KJZDK20240130 and Chongqing University of Arts and Sciences under Grant No. P2022SX09.

Conflict of interest

The authors declare no conflict of interest.

References:

D. Arquès. Relations fonctionnelles et dénombrement des cartes pointées sur le tore. Journal of Combinatorial Theory, Series B, 43:253–274, 1987. https://doi.org/10.1016/0095-8956(87)90002-5.
E. A. Bender and L. B. Richmond. A survey of the asymptotic behaviour of maps. Journal of Combinatorial Theory, Series B, 40:297–329, 1986. https://doi.org/10.1016/0095-8956(86)90086-9.
E. A. Bender and N. C. Wormald. The asymptotic number of rooted nonseparable maps on a given surface. Journal of Combinatorial Theory, Series A, 49:370–380, 1988. https://doi.org/10.1016/0097-3165(88)90063-5.
W. G. Brown. Enumeration of triangulations of the disc. Proceedings of the London Mathematical Society, 14:746–768, 1964. https://doi.org/10.1112/plms/s3-14.4.746.
J. L. Cai and Y. P. Liu. Enumeration on nonseparable planar maps. European Journal of Combinatorics, 23:881–889, 2002. https://doi.org/10.1006/eujc.2002.0569.
J. L. Cai and Y. P. Liu. The number of rooted eulerian planar maps. Science in China, Series A, 51:2005–2012, 2008. https://doi.org/10.1007/s11425-008-0064-5.
G. Chapuy and M. Dolega. A bijection for rooted maps on general surfaces. Journal of Combinatorial Theory, Series A, 145:252–307, 2017. https://doi.org/10.1016/j.jcta.2016.08.001.
Z. C. Gao. The number of rooted 2-connected triangular maps on the projective plane. Journal of Combinatorial Theory, Series B, 53:130–142, 1991. https://doi.org/10.1016/0095-8956(91)90058-R.
Z. C. Gao. The asymptotic number of rooted 2-connected triangular maps on a surface. Journal of Combinatorial Theory, Series B, 54:102–112, 1992. https://doi.org/10.1016/0095-8956(92)90068-9.

V. A. Liskovets. Enumeration of nonisomorphic planar maps. Selecta Mathematica, Soviet Union, 4:304–323, 1985.
V. A. Liskovets and T. R. S. Walsh. Enumeration of eulerian and unicursal planar maps. Discrete Mathematics, 282:209–221, 2004. https://doi.org/10.1016/j.disc.2003.09.015.
Y. P. Liu. On the number of rooted c-nets. Journal of Combinatorial Theory, Series B, 36:118–123, 1984. https://doi.org/10.1016/0095-8956(84)90018-2.
Y. P. Liu. On functional equations arising from map enumerations. Discrete Mathematics, 123:93–109, 1993. https://doi.org/10.1016/0012-365X(93)90009-I.
Y. P. Liu. Enumerative Theory of Maps. Kluwer, Boston, 1999.
M. Bousquet-Mélou and J. Courtiel. Spanning forests in regular planar maps. Journal of Combinatorial Theory, Series A, 135:1–59, 2015. https://doi.org/10.1016/j.jcta.2015.04.002.
M. Bousquet-Mélou and A. Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. Journal of Combinatorial Theory, Series B, 96:623–672, 2006. https://doi.org/10.1016/j.jctb.2005.12.003.
A. Mednykh and R. Nedela. Enumeration of unrooted maps of a given genus. Journal of Combinatorial Theory, Series B, 96:706–729, 2006. https://doi.org/10.1016/j.jctb.2006.01.005.
A. Mednykh and R. Nedela. Enumeration of unrooted hypermaps of a given genus. Discrete Mathematics, 310:518–526, 2010. https://doi.org/10.1016/j.disc.2009.03.033.

R. C. Mullin. Enumeration of rooted triangular maps. American Mathematical Monthly, 71:1007–1010, 1964. https://doi.org/10.2307/2311917.
R. C. Mullin. On counting rooted triangular maps. Canadian Journal of Mathematics, 17:373–382, 1965. https://doi.org/10.4153/CJM-1965-038-x.
W. T. Tutte. A census of planar triangulations. Canadian Journal of Mathematics, 14:21–38, 1962. https://doi.org/10.4153/CJM-1962-002-9.
W. T. Tutte. A census of slicings. Canadian Journal of Mathematics, 14:708–722, 1962. https://doi.org/10.4153/CJM-1962-061-1.
T. R. S. Walsh, A. Giorgetti, and A. Mednykh. Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices. Discrete Mathematics, 312:2660–2671, 2012. https://doi.org/10.1016/j.disc.2011.11.027.
E. T. Whittaker and G. N. Watson. A Course of Modern Analysis. Cambridge University Press, Cambridge, 1940. https://doi.org/10.1017/CB09780511608759.

[1] D. Arquès. Relations fonctionnelles et dénombrement des cartes pointées sur le tore. Journal of Combinatorial Theory, Series B, 43:253–274, 1987. https://doi.org/10.1016/0095-8956(87)90002-5.

[2] E. A. Bender and L. B. Richmond. A survey of the asymptotic behaviour of maps. Journal of Combinatorial Theory, Series B, 40:297–329, 1986. https://doi.org/10.1016/0095-8956(86)90086-9.

[3] E. A. Bender and N. C. Wormald. The asymptotic number of rooted nonseparable maps on a given surface. Journal of Combinatorial Theory, Series A, 49:370–380, 1988. https://doi.org/10.1016/0097-3165(88)90063-5.

[4] W. G. Brown. Enumeration of triangulations of the disc. Proceedings of the London Mathematical Society, 14:746–768, 1964. https://doi.org/10.1112/plms/s3-14.4.746.

[5] J. L. Cai and Y. P. Liu. Enumeration on nonseparable planar maps. European Journal of Combinatorics, 23:881–889, 2002. https://doi.org/10.1006/eujc.2002.0569.

[6] J. L. Cai and Y. P. Liu. The number of rooted eulerian planar maps. Science in China, Series A, 51:2005–2012, 2008. https://doi.org/10.1007/s11425-008-0064-5.

[7] G. Chapuy and M. Dolega. A bijection for rooted maps on general surfaces. Journal of Combinatorial Theory, Series A, 145:252–307, 2017. https://doi.org/10.1016/j.jcta.2016.08.001.

[8] Z. C. Gao. The number of rooted 2-connected triangular maps on the projective plane. Journal of Combinatorial Theory, Series B, 53:130–142, 1991. https://doi.org/10.1016/0095-8956(91)90058-R.

[9] Z. C. Gao. The asymptotic number of rooted 2-connected triangular maps on a surface. Journal of Combinatorial Theory, Series B, 54:102–112, 1992. https://doi.org/10.1016/0095-8956(92)90068-9.

Contents

Ars Combinatoria

Enumeration of rooted biloopless nonseparable planar near-triangulations

Abstract

1. Introduction

2. Functional equations

3. Enumeration

Acknowledgements

Conflict of interest

References:

Information

Guidelines

CP Initiatives

Follow CP