zbMATH — the first resource for mathematics

Counting unrooted loopless planar maps. (English) Zbl 1070.05050
This paper is devoted to proving the following formula for $$L^+(n)$$, the number of loopless planar maps with $$n$$ edges up to an orientation-preserving isomorphism:
Theorem 1. For $$n\geq1$$, $L^+(n)=\frac1{2n}\Biggl[ \frac{2(4n+1)}{(n+1)(3n+1)(3n+2)} \binom{4n} {n}+ \sum_{t<n,t|n}\phi \biggl(\frac nt \biggr) \binom{4t}{t}+ \begin{cases} \frac{2n}{n+1}{2n\choose \frac{n-1}2} \!&\! \text{if $$n$$ is odd}\\ \binom{2n} {\frac{n-2}2} \!&\! \text{if $$n$$ is even} \end{cases} \Biggr]\!,$ where $$\phi(n)$$ is the Euler totient function.

MSC:
 05C30 Enumeration in graph theory
Full Text:
References:
 [1] Bender, E.A.; Wormald, N.C., The number of loopless planar maps, Discrete math., 54, 2, 235-237, (1985) · Zbl 0563.05032 [2] Bóna, M.; Bousquet, M.; Labelle, G.; Leroux, P., Enumeration of m-ary cacti, Adv. appl. math., 24, 1, 22-56, (2000) · Zbl 0957.05056 [3] Bousquet, M.; Labelle, G.; Leroux, P., Enumeration of planar two-face maps, Discrete math., 222, 1-25, (2000) · Zbl 0993.05089 [4] Bousquet-Mélou, M.; Schaeffer, G., Enumeration of planar constellations, Adv. appl. math., 24, 4, 337-368, (2000) · Zbl 0955.05004 [5] Jones, G.A.; Singerman, D., Theory of maps on orientable surfaces, Proc. London math. soc. (3), 37, 2, 273-307, (1978) · Zbl 0391.05024 [6] Labelle, G., Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. math., 42, 217-247, (1981) · Zbl 0477.05007 [7] Liskovets, V.A., A census of non-isomorphic planar maps, (), 479-494, Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam, New York, 1981 · Zbl 0519.05040 [8] (Trans. from: Enumeration of nonisomorphic planar maps (Russian). I, Problems in Group Theory and Homological Algebra, 103-115, Yaroslav. Gos. Univ., Yaroslavl, 1981; II, Geometric Methods in Problems in Analysis and Algebra, 106-117, 129, 132, Yaroslav. Gos. Univ., 1981) · Zbl 0578.05033 [9] Liskovets, V., Reductive enumeration under mutually orthogonal group actions, Acta appl. math., 52, 91-120, (1998) · Zbl 0908.05003 [10] V.A. Liskovets, Enumerative formulae for unrooted planar maps: a pattern, 2004 (submitted for publication) · Zbl 1060.05046 [11] Liskovets, V.A.; Walsh, T.R.S., The enumeration of non-isomorphic 2-connected planar maps, Canad. J. math., 35, 3, 417-435, (1983) · Zbl 0519.05041 [12] Liskovets, V.A.; Walsh, T.R.S., Ten steps to counting planar graphs, Congr. numer., 60, 269-277, (1987) · Zbl 0647.05030 [13] Liskovets, V.A.; Walsh, T.R.S., Enumeration of Eulerian and unicursal planar maps, Discrete math., 282, 209-221, (2004) · Zbl 1051.05049 [14] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 2, 249-271, (1963) · Zbl 0115.17305 [15] Walkup, W., The number of planar trees, Mathematika, 19, 2, 200-204, (1972) · Zbl 0253.05106 [16] Walsh, T.R.S., Generating nonisomorphic maps without storing them, SIAM J. algebr. discrete methods, 4, 2, 161-178, (1983) · Zbl 0521.05034 [17] Walsh, T.R.S., Efficient enumeration of sensed maps, Discrete. math., (2003), (in press) [18] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus. III: non-separable maps, J. combin. theory ser. B, 18, 3, 222-259, (1975) · Zbl 0299.05110 [19] Wormald, N.C., A correspondence for rooted planar maps, Ars combin., 9, 11-28, (1980) · Zbl 0467.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.