Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 1–12
A note on enumeration of one-vertex maps∗
Alen Orbanić , Marko Petkovšek
Tomaž Pisanski †, Primož Potočnik
Institute of Mathematics, Physics and Mechanics and
Faculty of Mathematics and Physics, University of Ljubljana
Jadranska 19, SI-1000 Ljubljana, Slovenia
Received 29 December 2008, accepted 18 December 2009, published online 9 January 2010
Abstract
Explicit formulæ for the numbers of distinct maps and pre-maps having a single vertex
of valence d are given. The question of what precisely is meant by a map can be answered
in several different ways. We enumerate 16 different types of objects where each type is
obtained by selecting whether the object is a pre-map or a map, is oriented or general,
whether the underlying graph or pre-graph is signed or unsigned, is directed or undirected.
Keywords: Oriented maps and pre-maps, orientable maps and pre-maps, non-orientable maps and
pre-maps, pre-graphs, matchings in complete graphs, Cauchy-Frobenius-Burnside lemma.
Math. Subj. Class.: 05C10, 05C30
1 Introduction
It may seem that enumerating one-vertex maps looks rather sterile. On the other hand, a
natural approach to vertex-transitive maps, such as Cayley maps (see Malnič, Nedela and
Škoviera [17] and Richter, Širáň, Jajcay, Tucker and Watkins [21]), is to take the quotient
by the automorphism group, or a transitive subgroup of the automorphism group, which
automatically gives a one-vertex map. Thus any understanding of vertex-transitive maps
depends on an understanding of one-vertex maps. Furthermore, taking quotients by group
actions leads to a variety of “degenerate” structures, like semi-edges, which might not arise
from an intuitive idea of a map and which have not been treated consistently and uniformly
in the study of maps. The purpose of this paper is to provide a general setting for maps
∗The authors acknowledge partial funding of this research by ARRS of Slovenia, grants: L2-7230, P1-0294,
L2-7207 and the PASCAL network of excellence in the 6th framework.
†Joint position at the University of Primorska.
E-mail addresses: alen.orbanic@fmf.uni-lj.si (Alen Orbanić), marko.petkovsek@fmf.uni-lj.si (Marko
Petkovšek), tomaz.pisanski@fmf.uni-lj.si (Tomaž Pisanski), primoz.potocnik@fmf.uni-lj.si (Primož Potočnik)
Copyright c© 2010 DMFA Slovenije
2 Ars Math. Contemp. 3 (2010) 1–12
allowing such degenerate structures from the outset, and then using that setting to analyse
and enumerate one-vertex maps.
We should make it clear that the theory of combinatorial maps has a rich history. Unfor-
tunately, there were several equivalent, but not identical, approaches to maps introduced in
the past. In particular, treatment of oriented maps (on orientable surfaces) is much simpler
than the treatment of general maps that may result in orientable or non-orientable surfaces.
When considering maps as graphs, embedded in surfaces, the approach by Heffter [11],
later formalized by Stahl [26], with the so-called generalized embedding scheme for gen-
eral maps (orientable or not) is quite useful. The reader is referred to the three classical
textbooks in topological graph theory; see [22, 8, 31]. Unfortunately, this approach was
not developed for pre-maps, i.e., maps with underlying pre-graphs admitting semi-edges.
An alternative way of presenting maps is via specifying three involutions [5].
Let us also point out that the field of enumeration of maps, even one-vertex maps,
is very rich and well-established. Certain problems of enumerating isomorphism classes
of one-vertrex maps were addressed by Gross, Robbins and Tucker in [7], by Cori and
Marcus in [4], by Stoimenow in [28], by Khruzin in [13]1, by Kwak and Shim in [14],
and by Chapuy in [2]. An approach using advanced techniques, such as moduli spaces,
was suggested in a well-known work by Harer and Zagier [10], where they compute the
number of one-vertex maps, not only according to the number of edges but according to
the number of edges AND the number of faces (i.e., the genus of the surface). We would
like to make it clear that maps in this paper are not being counted by genus; the formulæ
give the total number of maps of orientable genus g over all possible g. In the case of
pre-maps, we also count the maps on surfaces with boundary. In the case of general maps,
the enumeration also applies to the non-orientable genus.
Also, there are now several bijective interpretations of the enumerative formulæ found
by Harer and Zagier, in particular by Goulden and Nica [6]. The reader is referred to the
work of Liskovets such as [15] where he develops techniques similar to ours. Standard
counting techniques to enumerate simple structures (like dissections of a polygon) up to
symmetry can be found, for instance, in the book by Harary and Palmer [9]. Similarly,
check the work of Walsh and Lehman [30] and Robinson [23].
In this article, we consider three distinct boolean parameters giving rise to eight enu-
meration problems:
First, we distinguish between maps and pre-maps. This parameter is needed since we
are mostly interested in counting pre-maps, but topologically maps are more natural ob-
jects. Note that maps correspond to Cayley graphs with no involutory generators.
The second parameter is the choice of directed vs. undirected loops. In our setting
this corresponds to the choice whether we consider Cayley graphs as directed or not, or
equivalently, whether we select in each pair consisting of a generator and its inverse one
element as the “preferred one”.
Our final parameter is the possibility to give a sign to some loops. Such a sign defines
a “twist” in the regular neighborhood of the corresponding non-involutory generator of
the Cayley graph, thereby extending the definition of the Cayley map to non-orientable
surfaces. Note that the actual Cayley map may still reside on an orientable surface (if the
order of the generator is even, and some other conditions are met; see for instance [8].) The
fact that the graph is signed or not is not a big problem in enumeration of one-vertex maps.
1Note that the value given in [13, p. 8] for d11 = δS̄D̄P̄ (22) is incorrect.
A. Orbanić et al.: A note on enumeration of one-vertex maps 3
It just consists in giving one of two possible colors (say red or blue) to each loop. This
makes it equivalent with enumeration of loop-bicolored (oriented!) maps.
We introduce a structure that we call a pre-graph; see also [17]. A pre-graph G is a
quadruple G = (V,A, i, r) where V is the set of vertices, A is the set of arcs (also known
as semi-edges, darts, sides, ...), i is the initial mapping i : A → V specifying the origin
or initial vertex for each arc, while r is the reversal involution: r : A → A, r2 = 1.
We may also define the terminal mapping t : A → V as t(s) := i(r(s)), specifying the
terminal vertex for each arc. An arc s forms an edge e = {s, r(s)}, which is called proper
if |e| = 2 and is called a half-edge if |e| = 1. Define ∂(e) = {i(s), t(s)}. A pre-graph
without half-edges is called a (general) graph. Note that G is a graph if and only if the
reversal involution has no fixed points. A proper edge e with |∂(e)| = 1 is called a loop
and two edges e, e′ are parallel if ∂(e) = ∂(e′). A graph without loops and parallel edges
is called simple. The valence of a vertex v is defined as val(v) = |{s ∈ A|i(s) = v}|. All
pre-graphs in this note are connected unless stated otherwise.
Topologically, an oriented map is a 2-cell embedding of a graph into an oriented closed
surface. However, in this paper we will operate with the following combinatorial descrip-
tion. For us an oriented pre-map is a triple (A, r,R) where A is a finite non-empty set
of darts and r, R are permutations on A such that r2 = 1 and 〈r,R〉 acts transitively on
A (see [17], but the description goes back to Jacques [12] and Cori [3]). Note that the
vertices of the pre-map correspond to the cycles in the cyclic decomposition of R. An
isomorphism between two pre-maps (A, r,R) and (A′, r′, R′) is any bijection π : A→ A′
for which πR = R′π and πr = r′π holds. An automorphism of a map (A, r,R) is thus a
permutation of A which commutes with both R and r. If r is fixed-point free, the structure
is called an oriented map rather than a pre-map. Combinatorial oriented maps correspond
to topological maps on oriented closed surfaces while oriented pre-maps correspond to
topological maps on surfaces with boundary (with a natural orbifold structure). To each
oriented pre-map M = (A, r,R) we may associate a unique map with reversed orientation
M−1 = (A, r,R−1). Each oriented map gives rise to the automorphism group Aut0(M)
of all (orientation-preserving) automorphisms, which can be extended to a larger group
Aut(M) by allowing the orientation-reversing automorphisms, i.e., isomorphisms from
(A, r,R) to (A, r,R−1). Note that the index of Aut0(M) in Aut(M) is either 1 or 2. If it
is 1 then M is chiral.
In addition to oriented maps we will also consider general (possibly non-orientable)
(pre-)maps, which can be defined as M = (A, r,R, λ), where A, r and R are as in the
definition of oriented maps, and λ is a sign mapping assigning either 1 or−1 to each proper
edge of the underlying pre-graph of the map M . Recall that each cycle C = (s1, . . . , sk)
of R corresponds to a vertex of the map. Substituting the cycle C in R with its reverse
cycle and inverting the λ-value of proper edges underlying the darts s1, . . . , sk other than
loops, results in a new map M ′, which is said to be obtained from M by a local orientation
change. Two maps M1 = (A1, r1, R1, λ1) and M2 = (A2, r2, R2, λ2) are isomorphic if
there exists a map M ′ = (A1, r1, R′, λ′) obtained from M1 by a series of local orientation
changes, and a bijection π : A1 → A2, such that πr1 = r2π, πR′ = R2π and λ′ =
λ2π. One of the early definitions of general maps goes back to Tutte [29], his definition is
equivalent to ours.
Note that in the topological interpretation a general pre-map resides in a surface that
may be orientable or non-orientable. There is a well-known condition for testing the ori-
entability of this surface. Namely the underlying surface is non-orientable if and only if
4 Ars Math. Contemp. 3 (2010) 1–12
there is a cycle with the product of signs λ along its edges equal to −1.
There is a well-known relationship between oriented maps and maps that reside on
orientable surfaces, namely each pair of oriented maps (A, r,R) and (A, r,R−1) gives rise
to the same map (A, r,R, λ) where λ is the constant 1, while each orientable map admits a
representation of such form and gives rise to two oriented maps: (A, r,R) and (A, r,R−1).
In case of embeddings of directed graphs or pre-graphs we may speak, respectively, of
directed maps or directed pre-maps.
We refer the reader to [20] for further details on the theory of maps and embeddings of
graphs and pre-graphs into surfaces. For the theory of Cayley maps, see for instance [21].
An overview of a combinatorial approach to coverings of graphs and pre-graphs was given
in [19].
The main combinatorial tool that we use in this paper is the classical orbit-counting
lemma of Cauchy and Frobenius, which can also be found in Burnside’s book [1].
Lemma 1.1. Let α be an action of a finite group G on a finite set A, ∼α the associated
equivalence relation on A, |A/∼α | the number of orbits of α, and Fixα(g) the set of
elements of A fixed by g ∈ G under α. Then
|A/∼α| =
1
|G|
∑
g∈G
|Fixα(g)|.
For a proof, see, e.g., [27, Lemma 7.24.5].
Denote by γτ (d) the number of non-isomorphic one-vertex oriented (pre-)maps of type
τ and valence d, and by δτ (d) the number of non-isomorphic one-vertex (orientable or non-
orientable) (pre-)maps of type τ and valence d. The types of (pre-)maps that we consider
are S̄D̄P̄ , SD̄P̄ , S̄DP̄ , S̄D̄P , SDP̄ , SD̄P , S̄DP , and SDP , indicating whether the
underlying (pre-)graphs are signed or unsigned (S resp. S̄), directed or undirected (D resp.
D̄), pre-graphs or graphs (P resp. P̄ ). We write τ = τ1τ2τ3 in order to be able to refer
to the individual symbols which constitute the type τ . As it turns out, γτ (d), δτ (d) and
the various auxiliary functions can be written in the same general form for all τ , but with
different values of parameters (see Eqn. (2.1) for γτ (d), Eqns. (3.1), (2.4), (3.3), and (3.2)
for δτ (d), and Table 1 for the values of parameters).
Each oriented one-vertex pre-map is isomorphic to one of the form (A, r,R) where
A = {1, 2, . . . , d}, R = (1, 2, . . . , d). Such a pre-map can be represented by a matching in
the complete graph Kd (possibly an empty one) in which two vertices i, j ∈ {1, 2, . . . , d}
are matched whenever r(i) = j. Hence the number of all one-vertex pre-maps (A, r,R)
with a given rotation R is the same as the number of all matchings (including the empty
one) in Kd. This number is easily computed to be
i(d) =
∑
0≤2k≤d
(
d
2k
)
(2k − 1)!!.
Of course, many of the above pre-maps are isomorphic. To compute the number of
non-isomorphic ones, let Id denote the set of all permutations r on A with r2 = 1, and
recall that two oriented pre-maps M = (A, r,R) and M ′ = (A, r′, R) are isomorphic if
and only if there exists a permutation on A which centralizes (= commutes with) R and
conjugates r to r′. Note that the permutations of A that centralize R (the centralizer of R)
form the cyclic group Cn, generated by R. However, if orientable maps are considered as
A. Orbanić et al.: A note on enumeration of one-vertex maps 5
general maps that reside on orientable surfaces, then the maps (A, r,R) and (A, r,R−1)
are isomorphic. In this case, an automorphism of the map is any permutation of A which
either commutes with R, or maps R to R−1. Such permutations form the dihedral group
Dd of order 2d, therefore the number of orientable non-isomorphic one-vertex pre-maps of
valence d equals the number of orbits of Dd in its action on the set Id by conjugation. If
the pre-maps are represented by the matchings in Kd, as described above, then the action
of Dd on Id corresponds to the natural action of Dd on the set of all matchings in Kd. In
general, the number δτ (d) of non-isomorphic one-vertex pre-maps of type τ and valence d
equals the number of orbits of Dd in its natural action on the set of matchings of type τ in
Kd. By Lemma 1.1 we thus have:
γτ (d) =
1
|Cd|
∑
σ∈Cd
|Fixτ (σ)|, (1.1)
δτ (d) =
1
|Dd|
∑
σ∈Dd
|Fixτ (σ)| (1.2)
where Fixτ (σ) denotes the set of matchings of type τ in Kd fixed by σ.
In all our formulæ we use the convention that 00 = 1, and define the double-factorial
function recursively: n!! = n× (n− 2)!! for n ≥ 1, 0!! = (−1)!! = 1.
2 Cyclic symmetry: Enumeration of oriented maps and pre-maps
Before we consider maps and pre-maps, we present simple formulæ for counting one-vertex
pre-graphs and graphs.
Let p(d) denote the number of one-vertex pre-graphs of valence d. Since each of them
is determined by the number of loops, p(d) = bd/2c+ 1. This gives rise to the generating
function P (x) = 1/((1− x)2(1 + x)) = 1/((1− x2)(1− x)).
If there are no pending edges, the situation becomes much simpler. Let g(d) denote the
number of one-vertex graphs. Then g(d) = 0, for d odd, and g(d) = 1, for d even. The
corresponding generating function is G(x) = 1/(1− x2).
When extending our enumeration exercise we note immediately that the number of one-
vertex digraphs is the same as the number of one-vertex graphs. Also, the number of one-
vertex directed pre-graphs is the same as the number of one-vertex pre-graphs. Similarly,
the number of one-vertex signed digraphs is the same as the number of one-vertex signed
graphs, and the number of one-vertex signed directed pre-graphs is the same as the number
of one-vertex signed pre-graphs. It is not hard to verify that the number of one-vertex
signed graphs of valence d is 0 if d is odd and d/2 + 1 if d is even. The corresponding
generating function is given by 1/(1− x2)2. The number of one-vertex signed pre-graphs
is given by 1 + 2 + · · ·+ (bd/2c+ 1) = (bd/2c+ 1)(bd/2c+ 2)/2 with the corresponding
generating function 1/((1− x)3(1 + x)2) = 1/((1− x2)2(1− x)).
Theorem 2.1. The number γτ (d) of oriented non-isomorphic one-vertex pre-maps resp.
maps of type τ and valence d is
γτ (d) =
1
d
∑
r|d
ϕ
(
d
r
) ∑
0≤2j≤r
(
r
2j
)
(2j − 1)!!
(
tτd
r
)j
wτ (r, d)r−2j (2.1)
where tτ is given in Table 1 and wτ (r, d) is shown in (2.3) below.
6 Ars Math. Contemp. 3 (2010) 1–12
Proof. As argued in the Introduction, γτ (d) equals the number of orbits of the cyclic group
Cd in its natural action on the set of matchings of type τ in the complete graph Kd, repre-
sented as a regular d-gon with diagonals. By (1.1),
γτ (d) =
Rτ (d)
d
(2.2)
whereRτ (d) is the sum over all σ ∈ Cd of the numbers of matchings of type τ inKd which
are fixed by σ. To compute this number, assume that σ ∈ Cd is the counter-clockwise
rotation by 2πkσ/d where kσ ∈ Z is such that 0 ≤ kσ < d. In how many ways can one
construct a matching M of Kd which is fixed by σ?
Let r = gcd(d, kσ). Then σ has r orbits in V (Kd), each containing d/r vertices. Let
C denote a set of r consecutive vertices of Kd. Since C contains one representative from
each orbit, it suffices to defineM on C, and to extend it to V (Kd)\C by symmetry. Hence
we can also think of M as a matching of orbits. Assume that 2j of the r orbits are matched
in pairs, while the rest remain unmatched or are matched with themselves (the latter is
possible only if antipodal vertices belong to the same orbit, i.e., if d is even and r divides
d/2). There are
(
r
2j
)
ways to select the 2j orbits, and (2j − 1)!! ways to group them into
pairs. In each of the j pairs of orbits (αi, βi), i = 1, 2, . . . , j, the vertex in αi ∩ C can be
matched with any of the d/r vertices in βi in tτ ways, where the value of tτ depends on the
type τ of the problem considered, and is shown in Table 1. Each of the remaining r − 2j
τ S̄D̄P̄ SD̄P̄ S̄DP̄ SDP̄ S̄D̄P SD̄P S̄DP SDP
sτ 1 2 0 0 2 3 1 1
tτ 1 2 2 4 1 2 2 4
mτ 1 2 2 4 2 3 3 5
Table 1: The values of sτ , tτ ,mτ for the types of (pre-)maps considered
orbits can be matched to themselves (or be left unmatched) in wτ (r, d) ways where
wτ (r, d) =
 sτ , r | (d/2),0, r 6 | (d/2) and τ3 = P̄ ,1, r 6 | (d/2) and τ3 = P, (2.3)
and the value of sτ is given in Table 1. For each divisor r of d, there are ϕ(d/r) rotations
σ in Dd having gcd(d, kσ) = r where ϕ denotes Euler’s totient function. Hence the total
contribution Rτ (d) of the d rotations is
Rτ (d) =
∑
r|d
ϕ
(
d
r
) ∑
0≤2j≤r
(
r
2j
)
(2j − 1)!!
(
tτd
r
)j
wτ (r, d)r−2j , (2.4)
and so by (2.2), we find that γτ (d) is as given in (2.1).
In Tables 2 and 3 we list the numbers γτ (d) for small values of d.
A. Orbanić et al.: A note on enumeration of one-vertex maps 7
d γS̄D̄P (d) γSD̄P (d) γS̄DP (d) γSDP (d)
1 1 1 1 1
2 2 3 2 3
3 2 3 3 5
4 5 11 8 21
5 6 17 17 57
6 18 69 60 299
7 34 187 187 1213
8 108 791 754 7189
9 294 2981 2981 36537
10 984 13575 13398 239027
11 3246 60851 60851 1412661
12 11810 301937 300982 10056109
13 43732 1513393 1513393 66657385
14 171218 8115273 8109584 510071643
15 689996 44293443 44293443 3711168173
16 2889970 254424929 254389122 30257794301
17 12458784 1490057537 1490057537 238049716833
18 55415816 9095634067 9095390802 2053738059275
19 253142182 56612205667 56612205667 17281059677029
20 1187979372 364845156207 364843436636 156892675044645
Table 2: The numbers of oriented non-isomorphic one-vertex pre-maps
d γS̄D̄P̄ (d) γSD̄P̄ (d) γS̄DP̄ (d) γSDP̄ (d)
2 1 2 1 2
4 2 6 4 14
6 5 28 22 164
8 18 234 218 3388
10 105 3112 3028 96776
12 902 55876 55540 3548876
14 9749 1237648 1235526 158146572
16 127072 32444680 32434108 8302721384
18 1915951 980254100 980179566 501851753292
20 32743182 33522615160 33522177088 34326661275896
22 624999093 1279939143784 1279935820810 2621308560998420
24 13176573910 53970651042864 53970628896500 221063688757926232
Table 3: The numbers of oriented non-isomorphic one-vertex maps
8 Ars Math. Contemp. 3 (2010) 1–12
3 Dihedral symmetry: Enumeration of (non-)orientable maps and
pre-maps
Theorem 3.1. The number δτ (d) of non-isomorphic one-vertex pre-maps resp. maps of
type τ and valence d is
δτ (d) =
Rτ (d) + Fτ (d)
2d
(3.1)
where Rτ (d) is given in (2.4) above, and Fτ (d) is given in (3.3) below.
Proof. As argued in the Introduction, δτ (d) equals the number of orbits of the dihedral
group Dd in its natural action on the set of matchings of type τ in the complete graph Kd,
represented as a regular d-gon with diagonals. By (1.2), this is given by the right hand-side
of (3.1) where Rτ (d) is the sum over all rotations σ ∈ Dd, and Fτ (d) the sum over all
reflections σ ∈ Dd, of the numbers of matchings of type τ in Kd fixed by σ. We have
already computed Rτ (d) in (2.4), hence it only remains to compute Fτ (d). We distinguish
two cases according to the parity of d.
If d is even there are two types of reflections of the regular d-gon: either across a median
or across a main diagonal. Let σ be the reflection across a median, and let L denote the set
of n := d/2 vertices of Kd on one side of the median. Denote fτ (n) := |Fixτ (σ)|. For
each u ∈ L, denote by u′ its mirror image across the median. In a matching M which is
fixed by σ, u can be either
• left unmatched, or
• matched with u′, or
• matched with some v ∈ L \ {u}, provided that u′ is matched with v′, or
• matched with v′ for some v ∈ L \ {u}, provided that u′ is matched with v.
Denote by sτ the number of ways in which u can be matched with u′ (including leaving
it unmatched), and by tτ the number of ways in which u can be matched with v ∈ L \ {u}.
Because of symmetry, the number of ways in which u can be matched with v′ where v ∈
L\{u} is also tτ . The values of sτ and tτ depend on the type τ of the problem considered,
and are shown in Table 1.
Thus to construct all possible such matchings, select 2j vertices from among the n
vertices in L, then construct a perfect matching on these 2j vertices. This can be done in(
n
2j
)
(2j − 1)!! ways. There are 2tτ ways to match the two elements in each of the j pairs,
yielding a factor of (2tτ )j , and sτ ways to match each of the remaining n− 2j vertices to
its mirror image, yielding a factor of sn−2jτ . Hence
fτ (n) =
∑
0≤2j≤n
sn−2jτ (2tτ )
j
(
n
2j
)
(2j − 1)!! = n!
∑
0≤2j≤n
sn−2jτ t
j
τ
(n− 2j)!j!
. (3.2)
If σ is the reflection across a main diagonal, then |Fixτ (σ)| = mτ fτ (d/2− 1) where
mτ is the number of ways in which it is possible to match the two vertices on the mirror
with each other. The value of mτ is shown in Table 1.
If d is odd there is only one type of reflections, namely across the bisector of a side
of the d-gon, and |Fixτ (σ)| = fτ ((d − 1)/2) for pre-maps and 0 for maps. So the total
A. Orbanić et al.: A note on enumeration of one-vertex maps 9
contribution Fτ (d) of the d reflections to the sum in (1.2) is
Fτ (d) =

d
2
(
fτ
(
d
2
)
+mτ fτ
(
d
2
− 1
))
, d even,
d fτ
(
d− 1
2
)
, d odd and τ3 = P,
0, d odd and τ3 = P̄ ,
(3.3)
where fτ is given by (3.2), and mτ is shown in Table 1. This finishes the proof of the
theorem.
In Tables 4 and 5 we list the numbers δτ (d) for small values of d. For instance,
δS̄D̄P (5) = 6, so there are six pairwise non-isomorphic one-vertex undirected orientable
pre-maps of valence five (which, incidentally, are discussed in detail in [24]).
4 Concluding remarks
4.1 Additional formulæ
In the special case when wτ (r, d) = 0 for all r, the double sum in (2.4) reduces to a single
sum. For d even we thus have
RS̄DP̄ (d) =
∑
r|d, r even
ϕ
(
d
r
)
(r − 1)!!
(
2d
r
)r/2
,
RSDP̄ (d) =
∑
r|d, r even
ϕ
(
d
r
)
(r − 1)!!
(
4d
r
)r/2
.
It is not difficult to see that the sequence fτ (n) from (3.2) satisfies the recurrence
fτ (n) = sτ fτ (n− 1) + 2tτ (n− 1)fτ (n− 2), for n ≥ 2, (4.1)
with fτ (0) = 1, fτ (1) = sτ , and that its exponential generating function equals
∞∑
n=0
fτ (n)
xn
n!
= exp(sτ x+ tτ x2). (4.2)
Comparing this with the well-known exponential generating function of Hermite polyno-
mials
∞∑
n=0
Hn(t)
xn
n!
= exp(2tx− x2),
we see that
fτ (n) =
(
i
√
tτ
)n
Hn
(
sτ
2i
√
tτ
)
(4.3)
where i2 = −1 andHn(t) is the n-th Hermite polynomial. In the special case when sτ = 0,
the sum in (3.2) has a single term. Thus, for n even,
fS̄DP̄ (n) = 2
n(n− 1)!!,
fSDP̄ (n) = (2
√
2)n(n− 1)!!.
10 Ars Math. Contemp. 3 (2010) 1–12
d δS̄D̄P (d) δSD̄P (d) δS̄DP (d) δSDP (d)
1 1 1 1 1
2 2 3 2 3
3 2 3 2 3
4 5 11 6 14
5 6 15 11 33
6 17 60 37 167
7 27 125 100 619
8 83 529 405 3686
9 185 1663 1527 18389
10 608 7557 6824 120075
11 1779 31447 30566 706851
12 6407 155758 151137 5032026
13 22558 763211 757567 33334033
14 87929 4089438 4058219 255064335
15 348254 22190781 22150964 1855614411
16 1456341 127435846 127215233 15129137658
17 6245592 745343353 745057385 119025187809
18 27766356 4549465739 4547820514 1026870988199
19 126655587 28308456491 28306267210 8640532108675
20 594304478 182435301597 182422562168 78446356190934
Table 4: The numbers of non-isomorphic one-vertex pre-maps
d δS̄D̄P̄ (d) δSD̄P̄ (d) δS̄DP̄ (d) δSDP̄ (d)
2 1 2 1 2
4 2 6 3 9
6 5 26 13 90
8 17 173 121 1742
10 79 1844 1538 48580
12 554 29570 28010 1776358
14 5283 628680 618243 79080966
16 65346 16286084 16223774 4151468212
18 966156 490560202 490103223 250926306726
20 16411700 16764409276 16761330464 17163338379388
22 312700297 639992710196 639968394245 1310654311464970
24 6589356711 26985505589784 26985325092730 110531845060209836
Table 5: The numbers of non-isomorphic one-vertex maps
A. Orbanić et al.: A note on enumeration of one-vertex maps 11
4.2 Identification of sequences in OEIS
Some of the sequences encountered in this paper can be found in the The Online Encyclo-
pedia of Integer Sequences [25], to wit:
• 〈δS̄D̄P̄ (2n)〉∞n=1 is sequence A054499 in [25],
• 〈γS̄D̄P̄ (2n)〉∞n=1 is sequence A007769 in [25],
• 〈fS̄D̄P̄ (n)〉∞n=0 is sequence A047974 in [25],
• 〈fS̄D̄P (n)〉∞n=0 is sequence A000898 in [25],
• 〈fS̄DP (n)〉∞n=0 is sequence A115329 in [25],
• 〈fS̄DP̄ (2n− 2)〉∞n=1 is sequence A052714 in [25],
• 〈fSDP̄ (2n− 2)〉∞n=1 is sequence A052734 in [25].
4.3 Possible extensions
Using the methods of [18] one can easily extend the counting to graphs with one-vertex
connected components. For a more recent example of such methods, see also [16]. Moti-
vated by [14], it would be worthwhile to extend this analysis to dipoles or any two-vertex
graphs or pre-graphs.
5 Acknowledgements
The authors would like to thank T.W. Tucker for his helpful remarks and to the anonymous
referees for their valuable suggestions which helped improve the quality of the paper.
References
[1] W. Burnside, Theory of Groups of Finite Order, second ed. (1911), Cambridge University Press,
1897.
[2] G. Chapuy, The structure of unicellular maps, and a connection between maps of positive genus
and planar labelled trees, arXiv:0804.0546v2 [math.CO].
[3] R. Cori, Un code pour les graphes planaires et ses applications, Astérisque, No. 27, Société
Mathématique de France, Paris, 1975.
[4] R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theoret. Comput. Sci. 204
(1998), 55–73.
[5] C. D. Godsil and G. Royle, Algebraic Graph Theory, Springer Verlag, New York, Berlin, Hei-
delberg, 2001.
[6] I. P. Goulden and A. Nica, A direct bijection for Harer-Zagier formula, J. Combin. Theory Ser.
A 111 (2005), 224–238.
[7] J. Gross, D. P. Robbins and T. W. Tucker, Genus distributions for bouquets of circles, J. Combin.
Theory Ser. B 47 (1989), 292–306.
[8] J. Gross and T. W. Tucker, Topological Graph Theory, Wiley Interscience, 1987.
[9] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.
[10] J. Harer and D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math. 85
(1986), 457–486.
[11] L. Heffter, Über das Problem der Nachbargebiete, Math. Ann. 38 (1891), 477–508.
12 Ars Math. Contemp. 3 (2010) 1–12
[12] A. Jacques, Sur le genre d’une paire de substitutions, C. R. Acad. Sci. Paris 267 (1968), 625–
627.
[13] A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209v1 [math.CO].
[14] J. H. Kwak and S. H. Shim, Total embedding distributions for bouquets of circles, Discrete
Math. 248 (2002), 93–108.
[15] V. A. Liskovets, Reductive enumeration under mutually orthogonal group actions, Acta Appl.
Math. 52 (1998), 91–120.
[16] V. A. Liskovets and A. D. Mednykh, On the number of connected and disconnected coverings
over a manifold, Ars Math. Contemp. 2 (2009), 181–189.
[17] A. Malnič, R. Nedela and M. Škoviera, Regular homomorphisms and regular maps, Europ. J.
Combin. 23 (2002), 449–461.
[18] M. Petkovšek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes,
I-graphs, and others, Croat. Chem. Acta 78 (2005), 563–567.
[19] T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007), 567–578.
[20] T. Pisanski and P. Potočnik, Graphs on surfaces, in: J.L. Gross, J. Yellen (eds.), Handbook
of Graph Theory, The CRC Press Series on Discrete Mathematics and its Applications, CRC
Press, Boca Raton, 2004, 611–624.
[21] R. B. Richter, J. Širáň, R. Jajcay, T. W. Tucker and M. E. Watkins, Cayley maps, J. Combin.
Theory Ser. B 95 (2005), 189–245.
[22] G. Ringel, Map Color Theorem, Die Grundlehren der mathematischen Wissenschaften, Band
209, Springer-Verlag, New York-Heidelberg, 1974.
[23] R. W. Robinson, Counting perfect matchings with superposed directed cycles, presented at the
21st Cumberland Conference on Graph Theory, Combinatorics, and Computing — In Honor of
Mike Plummer’s 70th Birthday May 15-17, 2008, Vanderbilt University, Nashville, TN, USA
[24] J. Šiagiová and Mark E. Watkins, Covalence sequences of planar vertex-homogeneous maps,
Discrete Math. 307 (2007), 599–614.
[25] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at
http://www.research.att.com/˜njas/sequences/.
[26] S. Stahl, Generalized embedding schemes, J. Graph Theory 2 (1978), 41–52.
[27] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge
1999.
[28] A. Stoimenow, On the number of chord diagrams, Discrete Math. 218 (2000), 109–233.
[29] W. T. Tutte, What is a map?, New Directions in the Theory of Graphs (Proc. Third Ann Arbor
Conf., Univ. Michigan, Ann Arbor, Mich., 1971), pp. 309–325. Academic Press, New York,
1973.
[30] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Combin. Theory Ser. B
13 (1972), 192–218.
[31] A. T. White, Graphs of Groups on Surfaces, North-Holland Mathematics Studies 188, North-
Holland Publishing Co., Amsterdam 2001.