Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 181–189
On the number of connected and disconnected
coverings over a manifold
Valery A. Liskovets ∗
Institute of Mathematics, National Academy of Sciences of Belarus
Minsk, 220072, Belarus
Alexander D. Mednykh †
Sobolev Institute of Mathematics, Novosibirsk State University
Novosibirsk, 630090, Russia
Received 5 February 2009, accepted 4 September 2009, published online 30 September 2009
Abstract
A general formula is obtained for the number of non-equivalent coverings (possibly
disconnected) over a connected manifold with an arbitrary finitely generated fundamental
group. Some illustrative examples are considered.
Keywords: Counting homomorphisms, non-equivalent coverings, disconnected coverings, fundamen-
tal group; Euler transform.
Math. Subj. Class.: 57M10, 20F34, 05A15, 14H30
1 Introduction
Let p : U →M be an arbitrary (possibly disconnected) covering over a connected manifold
M. Then every path γ ∈ M has a unique lifting γ̃ starting at a given point of p−1(γ(0));
so we obtain a well-defined mapping Lγ : p−1(γ(0))→ p−1(γ(1)) by sending the starting
point γ̃(0) of each lifting γ̃ to its ending point γ̃(1). By the familiar monodromy theorem,
Lγ depends only on the homotopy class of γ. This means that the association γ 7→ Lγ
gives rise to a homomorphism from π1(M, x0) to a permutation group acting on the fiber
F = p−1(x0).We note that this action of π1(M, x0) is transitive if and only if the covering
∗Supported by the BRFFR (grant F07-293).
†Supported by the RFBR (grant 09-01-00255), APVV SK-RU-0007-07 and by Fondecyt (grants 7050189,
1060378).
E-mail addresses: liskov@im.bas-net.by (Valery A. Liskovets), mednykh@math.nsc.ru (Alexander D.
Mednykh)
Copyright c© 2009 DMFA Slovenije
182 Ars Math. Contemp. 2 (2009) 181–189
manifold U is connected. More generally, the number of orbits of the action coincides with
the number of connected components of the covering.
Two coverings p1 : U1 → M and p2 : U2 → M are equivalent if and only if the
corresponding actions of π1(M, x0) on the fibers F1 and F2 over x0 are isomorphic. This
shows that n-sheeted covering spaces overM are classified by equivalence classes of ho-
momorphisms ρ : π1(M, x0) → Sn, where Sn is the symmetric group on n symbols and
the equivalence relation imposes an equivalence between ρ and all its conjugates h−1ρh by
elements h ∈ Sn.
All the above-mentioned results remain valid for any path-connected, locally path-
connected and semilocally simply connected topological space M; see, for example [2,
Ch.1.3: Th.1.38]. In particular, they are valid for finite graphs.
In the present paper we count the number of all non-equivalent coverings (connected
or not) over a connected manifold with a finitely generated fundamental group. Then, by
making use of the standard Euler transform (see Lemma 2.6 below) we relate the number
of connected and disconnected coverings to get a new proof of the main result of [12].
This approach, which makes it possible to calculate the number of connected coverings
through the number of disconnected ones, is, essentially, new. Earlier, for the special cases
of the free group and the free product of cyclic groups, it has been effectively used in [4]
and [15] to enumerate graph coverings and ‘unsensed’ maps on closed orientable surfaces,
respectively.
Related general results for the enumeration of coverings were obtained by H. Tama-
noi [18] and by T. Müller and J. Shareshian [13].
Several preceding papers contain formulae for counting non-equivalent connected and
disconnected coverings. The numbers of non-equivalent connected and arbitrary coverings
of a graph were determined in [7] and [4], respectively. Connected coverings of closed
surface were counted in [10]. A general method to enumerate connected coverings over
manifolds was given in [11, 12]. In more detail, the enumeration of graphs and manifold
coverings (including disconnected ones) is considered in [6]. In [1], a relation between the
numbers of connected and disconnected weighted ramified coverings over a torus is derived
and used. Some enumerative applications of disconnected structures to chemistry are given
in [14].
2 Main results
The following theorem has been proved by the second-named author [11, 12].
Theorem 2.1. LetM be a connected manifold with a finitely generated fundamental group
Γ. Then the number un of non-equivalent connected n-fold coverings overM is given by
the formula
un =
1
n
∑
`|n
`m=n
∑
K<mΓ
|Epi(K,Z`)|, (2.1)
where the sum
∑
K<mΓ
is taken over all subgroups K of index m in the group Γ,
Epi(K, Z`) is the set of epimorphisms of the group K onto a cyclic group Z` of order
` and |X| denotes the cardinality of a set X.
The aim of the present paper is to extend this theorem to coverings that are not neces-
sarily connected.
V. A. Liskovets and A. D. Mednykh: On the number of connected and disconnected. . . 183
Theorem 2.2. LetM be a connected manifold with a finitely generated fundamental group
Γ. Denote by bn the number of all non-equivalent (connected or disconnected) n-fold cov-
erings overM and let B(x) = 1 + b1 x+ b2 x2 + · · · be the ordinary generating function
for these numbers. Then
B(x) = exp
( ∞∑
n=1
∑
`|n
`m=n
∑
K<mΓ
|Hom(K,Z`)|
xn
n
)
, (2.2)
where Hom(K, Z`) is the set of homomorphisms of the group K into a cyclic group Z`.
Proof. From Burnside’s lemma we obtain (reasoning similarly to [8]) the following result.
Lemma 2.3.
bn =
∑
c1+2c2+···+ncn=n
n∏
i=1
|Hom(Γ,Zi Wr Sci)|
ici ci!
, (2.3)
where AWrB is the standard wreath product of permutation groups A and B and Zi is
considered as a regular cyclic permutation group of order i.
Since n = c1 + 2c2 + · · ·+ ncn, we have from this lemma,
bnx
n =
∑
c1+2c2+···+ncn=n
n∏
i=1
|Hom(Γ,Zi Wr Sci)|
ici ci!
xici .
Hence, B(x) =
∏∞
i=1 bi(x), where
bi(x) =
∑
c≥0
|Hom(Γ,Zi WrSc)|
ic c!
xic.
The next lemma follows directly from formula (5) of [13].
Lemma 2.4. For any ` ≥ 1,∑
m≥0
|Hom(Γ,Z` Wr Sm)|
m!
xm = exp
( ∑
m≥1
`m−1
∑
K<mΓ
|Hom(K,Z`)|
xm
m
)
. (2.4)
Now we return to the proof of Theorem 2.2. Taking (2.4) into account we have
bi(x) =
∑
c≥0
|Hom(Γ,Zi Wr Sc)|
ic c!
xic =
∑
c≥0
|Hom(Γ,Zi Wr Sc)|
c!
(xi
i
)c
= exp
( ∑
m≥1
im−1
∑
K<mΓ
|Hom(K,Zi)|
m
(xi
i
)m)
= exp
( ∑
m≥1
∑
K<mΓ
|Hom(K,Zi)|
xim
im
)
.
Finally, we obtain
B(x) =
∞∏
i=1
bi(x) = exp
( ∞∑
i=1
∑
m≥1
∑
K<mΓ
|Hom(K,Zi)|
xim
im
)
184 Ars Math. Contemp. 2 (2009) 181–189
= exp
( ∞∑
n=1
∑
`|n
`m=n
∑
K<mΓ
|Hom(K,Z`)|
xn
n
)
.
As a consequence of Theorem 2.2 we can give a new proof of Theorem 2.1. To that end
we will make use of the following preliminary results [3]:
Lemma 2.5.
|Epi(K,Z`)| =
∑
d|`
µ
( `
d
)
|Hom(K,Z`)|,
where µ(n) is the number-theoretic Möbius function.
In enumerative combinatorics, there is a simple general formula1 (see, e.g., [19, Th.
3.14.1]) called the Euler transform [17, p. 20] that relates the generating function of ar-
bitrary, possibly disconnected, unlabeled objects of a certain kind with that of connected
objects of the same kind (serving as their independent “building blocks”). In terms of
coverings it is formulated as follows.
Lemma 2.6. Let ui and B(x) be defined as in Theorems 2.1 and 2.2, respectively. Then
the following identity is valid:
B(x) =
∞∏
i=1
(1− xi)−ui .
Proof. Denote by S the set of equivalence classes of all connected coverings of finite multi-
plicity over the manifoldM. Let D = NS be the set of all finite linear combinations of the
typem1C1 +m2C2 + . . .+mkCk, wherem1,m2, . . . ,mk ∈ N and C1, C2, . . . , Ck ∈ S.
We identify D with the set of equivalence classes of all coverings of finite multiplicity over
the manifoldM.
Define µ̂ : S → N to be the multiplicity of the covering. For any d = m1C1 +
m2C2 + . . .+mkCk ∈ D, we set µ̂(d) = m1 · µ̂(C1) +m2 · µ̂(C2) + . . .+mk · µ̂(Ck).
Then un = |(c ∈ S : µ̂(c) = n)| and bn = |(d ∈ D : µ̂(d) = n)| are the numbers of
equivalence classes of connected and all n-fold coverings, respectively.
Let Ci1, C
i
2, . . . , C
i
ai ∈ S be the list of equivalence classes of all i-fold connected cov-
erings for any i = 1, 2, . . . . Then any n-fold covering, up to equivalence, can be uniquely
represented as C =
n∑
i=1
ai∑
j=1
mijC
i
j for some non-negative integersm
i
j satisfying µ̂(C) = n.
Since µ̂(Cij) = i, the last condition is equivalent to
n∑
i=1
ai∑
j=1
i · mij = n. Hence, bn
coincides with the number of non-negative solution of above equation. We set also b0 = 1.
Then we have
bnx
n =
∑
n∑
i=1
ui∑
j=1
i·mij=n
n∏
i=1
ai∏
j=1
xi·m
i
j
1In applications to unlabeled graphs it is also known as Riddell’s formula.
V. A. Liskovets and A. D. Mednykh: On the number of connected and disconnected. . . 185
and, consequently,
B(x) = b0 + b1x+ b2x2 + . . . =
∞∏
i=1
(1 + xi + x2i + . . .)ui =
∞∏
i=1
(1− xi)−ui .
Now we are ready to prove Theorem 2.1 as a consequence of Theorem 2.2.
Proof. By Theorem 2.2 we have
B(x) = exp
( ∞∑
n=1
vn
xn
n
)
, (2.5)
where
vn =
∑
`|n
`m=n
∑
K<mΓ
|Hom(K,Z`)|.
By Lemma 2.6 we also have
B(x) =
∞∏
i=1
(1− xi)−ui . (2.6)
Then, combining (2.5) and (2.6) and taking the logarithm we obtain
∞∑
n=1
vn
xn
n
= −
∞∑
i=1
ui log(1− xi). (2.7)
After differentiating (2.7) and multiplying by x we get
∞∑
n=1
vn x
n =
∞∑
i=1
i uix
i
1− xi
.
Comparing the coefficients of the Taylor and Lambert series we have vn =
∑
j|n
j uj . Now,
by the Möbius inversion formula we obtain
nun =
∑
j|n
µ
(n
j
)
vj =
∑
j|n
µ
(n
j
)∑
m|j
∑
K<mΓ
∣∣Hom(K,Z j
m
)∣∣
=
∑
j|n
∑
m|j
∑
K<mΓ
µ
(n
j
)∣∣Hom(K,Z j
m
)∣∣
=
∑
m|n
∑
m|j|n
∑
K<mΓ
µ
(n
j
)∣∣Hom(K,Z j
m
)∣∣ = ∑
m|n
∑
K<mΓ
∑
m|j|n
µ
(n
j
)∣∣Hom(K,Z j
m
)∣∣
=
∑
`|n
`m=n
∑
K<mΓ
∑
d|`
µ
( `
d
)
|Hom(K,Zd)| =
∑
`|n
`m=n
∑
K<mΓ
|Epi(K,Z`)|
(the last equality follows from Lemma 2.5). This is formula (2.1).
186 Ars Math. Contemp. 2 (2009) 181–189
3 Examples
3.1 The number of not necessarily connected coverings over a circle
In this case, Γ = π1(S1) = Z, an infinite cyclic group. The total number of n-fold
coverings over the circle S1 is given by the standard partition function p(n), where
p(0) + p(1)x+ p(2)x2 + · · · =
∞∏
i=1
(1− xi)−1
(so that, p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11, . . .).
This is the well-known Euler equation. To derive it in the framework of our approach we
note that the group Z has only one subgroup of index n. Hence, un = 1 for every n ≥ 1,
and the result follows from Lemma 2.6.
3.2 The number of coverings over a graph
Let G be a finite connected graph with Betti number r = β(G). Then Γ = π1(G) = Fr
is a free group of rank r. By [7, 8] we have |Hom(Γ,Zi Wr Sci)| = (ici ci!)r. Hence, by
Lemma 2.3,
bn =
∑
c1+2c2+···+ncn=n
n∏
i=1
(ici ci!)r−1. (3.1)
This is a result by J. H. Kwak and Y. Lee [4]. It has been used to calculate the number
of connected coverings over a graph G. The latter coincides with the number of conjugacy
classes of subgroups of index n in the free group Fr obtained earlier in [7]. Thus, Theo-
rem 2.2 gives an affirmative answer to the question posed by J. H. Kwak [5] as to whether
(and how) it is possible to relate the enumerative results of papers [4] and [7].
3.3 The number of all coverings over a closed orientable surface
In this case we have
B(x) = exp
( ∞∑
n=1
∑
`|n
`m=n
`(2g−2)m+2MΦg (m)
xn
n
)
, (3.2)
where Φg is the fundamental group of a closed orientable surface of genus g andMΦg (n) is
the number of subgroups of index n in Φg . Indeed, by the Riemann-Hurwitz formula, any
subgroupK of indexm in the group Φg is isomorphic to Φg′ ,where (2g′−2) = (2g−2)m.
Now, the first homology group H1(Φg′) = Φg′/[Φg′ , Φg′ ] is equal to Z2g
′
= Z(2g−2)m+2
and |Hom(K,Z`)| = |Hom(H1(K),Z`)| = `(2g−2)m+2. Therefore,∑
K<mΓ
|Hom(K,Z`)| = `(2g−2)m+2MΦg (m).
Substituting this equality into the statement of Theorem 2.2 we obtain (3.2).
Recall [9] that MΦg (m) can be computed by the following linear recursion formula:
MΦg (m) = mβm −
m−1∑
j=1
βm−jMΦg (j), MΦg (1) = 1, (3.3)
V. A. Liskovets and A. D. Mednykh: On the number of connected and disconnected. . . 187
where
βk =
∑
χ∈Dk
( k!
fχ
)2g−2
, (3.4)
Dk is the set of all irreducible representations of the symmetric group Sk and fχ is the
degree of a representation χ.
Instead of (3.2), by the Euler transform (Lemma 2.6), we have immediately,
B(x) =
∞∏
i=1
(1− xi)−ui , (3.5)
where un = NΦg (n) denotes the number of connected n-fold coverings of a closed ori-
entable surface of genus g, which is equal to the number of conjugacy classes of subgroups
of index n in Φg found in [9, 10]. Equating the right-hand sides of (3.2) and (3.5), we
obtain the following equation for NΦg (n) in terms of generating functions:
∞∏
i=1
(1− xi)−NΦg (i) = exp
( ∞∑
n=1
∑
`|n
`m=n
`(2g−2)m+2MΦg (m)
xn
n
)
, g ≥ 0, (3.6)
which is equivalent to the explicit formula obtained in [9].
Let bn = DC(n, ν) be the total number of all non-equivalent n-fold coverings (con-
nected or disconnected) over a closed orientable surface of genus g, where ν = 2g − 2 is
its characteristic. Then by formula (3.2) we calculated for n = 1, . . . , 7:
DC(1, ν) = 1
DC(2, ν) = 4 · 2ν
DC(3, ν) = 2 · 6ν + 4 · 3ν + 2 · 2ν
DC(4, ν) = 2 · 24ν + 12ν + 6 · 8ν + 9 · 4ν + 3 · 3ν
DC(5, ν) = 2 · 120ν + 2 · 30ν + 2 · 24ν + 20ν + 4 · 12ν + 4 · 8ν + 14 · 6ν
+ 5 · 5ν + 5 · 4ν
DC(6, ν) = 2 · 720ν + 4 · 144ν + 2 · 80ν + 2 · 72ν + 8 · 48ν + 45ν + 4 · 24ν
+ 12 · 18ν + 16 · 16ν + 6 · 9ν + 18 · 8ν + 12 · 6ν + 5 · 5ν
DC(7, ν) = 2 · 5040ν + 2 · 840ν + 4 · 360ν + 2 · 336ν + 252ν + 6 · 240ν + 2 · 144ν
+ 6 · 72ν + 4 · 60ν + 16 · 48ν + 2 · 40ν + 3 · 36ν + 34 · 24ν + 6 · 18ν
+ 4 · 16ν + 32 · 12ν + 20 · 10ν + 3 · 9ν + 8 · 8ν + 7 · 7ν + 6 · 6ν .
Table 1 contains initial numerical values of the function DC(n, ν), ν ≥ −2. For com-
pleteness we included values for odd ν as well, in particular, fractional values for ν = −1.
The latter have a simple combinatorial meaning: DC(n,−1) = r2(n)/n!, where r(n) is
the sum of the degrees of the irreducible representations of the symmetric group Sn (cf.
formula (3.4)) 2.
2This is the sequence A000085 [16]. The generating function for r2(n)/n! is exp
(
x/(1− x)
)
/
√
1− x2,
and the values of r2(n) form the sequence A111883.
188 Ars Math. Contemp. 2 (2009) 181–189
ν g 1 2 3 4 5 6 7
−2 0 1 1 1 1 1 1 1
−1 – 1 2 16/3! 100/4! 676/5! 5776/6! 53824/7!
0 1 1 4 8 21 39 92 170
1 – 1 8 28 153 577 3612 19228
2 2 1 16 116 1851 33693 1175852 53529098
3 – 1 32 556 33105 3558577 761393916 257606692684
4 3 1 64 2948 711411 417285429 539383049612
5 – 1 128 16588 16380633 49835381257 387243914607612
6 4 1 256 96356 386803851 5973885950253
Table 1: Values of DC(n, ν) for ν ≤ 6 and n ≤ 7.
3.4 The number of coverings over a torus
In conclusion we address the particular case ν = 0. By [10] we have MΦ1(n) = σ(n),
where σ(n) =
∑
d|n
d is the sum of positive divisors of n. Setting g = 1 in formula (3.2) we
obtain
B(x) = exp
( ∞∑
n=1
∑
`|n
`m=n
` 2 σ(m)
xn
n
)
. (3.7)
Again, instead of (3.7), by the Euler transform we have
B(x) =
∞∏
i=1
(1− xi)−σ(i). (3.8)
Accordingly, bn = DC(n, 0), n ≥ 1, is the sequence A061256 [16], which starts with
1, 4, 8, 21, 39, 92, 170, 360, 667, 1316, 2393, 4541, 8100, 14824, 26071, 46422.
4 Acknowledgements
We thank the anonymous referees for reading our paper carefully and giving many helpful
suggestions concerning its text.
References
[1] A. Eskin and A. Okounkov, Asymptotics of numbers of branched coverings of a torus and
volumes of moduli spaces of holomorphic differentials, Invent. Math. 145 (2001), 59–103.
[2] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002.
[3] G. A. Jones, Enumeration of homomorphisms and surface-coverings, Quart. J. Math. Oxford
(2) 46 (1995), 485–507.
[4] J. H. Kwak and J. Lee, Enumeration of connected graph coverings, J. Graph Theory 23 (1996),
105–109.
[5] J. H. Kwak and J. Lee, Enumeration of graph coverings, surface branched coverings and related
group theory, in: S. Hong, J. H. Kwak et al. (eds.), Combinatorial Computational Mathematics:
Present and Future, Word Scientific, Singapore, 2001, 97–161.
[6] J. H. Kwak and A. D. Mednykh, Enumeration of Graphs and Manifold Coverings, Com2Mac
Lect. Notes, No. 19, Pohang: Pohang Univ. of Science and Technology, 2007.
V. A. Liskovets and A. D. Mednykh: On the number of connected and disconnected. . . 189
[7] V. A. Liskovets, On the enumeration of subgroups of a free group, Dokl. Akad. Nauk BSSR 15
(1971), 6–9.
[8] V. A. Liskovets, Reductive enumeration under mutually orthogonal group actions, Acta Applic.
Math. 52 (1998), 91–120.
[9] A. D. Mednykh, On the Hurwitz problem on the number of nonequivalent coverings over a
compact Riemann surface, Sib. Math. J. 23 (1983), 415–420; translation from Sib. Mat. Zh. 23
(1982), 155–160.
[10] A. D. Mednykh, On the number of subgroups in the fundamental group of a closed surface,
Commun. Algebra 16 (1988), 2137–2148.
[11] A. D. Mednykh, A new method for counting coverings over manifold with finitely generated
fundamental group, Doklady Mathematics 74 (2006), 498–502; translation from Dokl. Akad.
Nauk 409 (2006), 158–162.
[12] A. D. Mednykh, Counting conjugacy classes of subgroups in a finitely generated group, J.
Algebra 320 (2008), 2209–2217.
[13] T. W. Müller and J. Shareshian, Enumerating representations in finite wreath products, II: Ex-
plicit formulae, Adv. Math. 171 (2002), 276–331.
[14] M. Petkovšek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes,
I-graphs, and others, Croatica Chemica Acta 78 (2005), 563–567.
[15] R. Robinson, Counting unrooted maps of all genera, Talk at the Twentieth Clemson Mini-
Conference on Discrete Math. and Related Fields, Oct. 2005,
http://www.cs.clemson.edu/˜goddard/MINI/2005/Robinson.pdf.
[16] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences (2009),
http://www.research.att.com/˜njas/sequences/.
[17] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, San
Diego, CA, 1995.
[18] H. Tamanoi, Generalized orbifold Euler characteristics of symmetric orbifolds and covering
spaces, Algebr. Geom. Topol. 3 (2003), 791–856 (electronic).
[19] H. S. Wilf, generatingfunctionology, Second edition, Academic Press, Boston, MA, 1994.