Total Vertex Enumeration in Rooted Planar Maps

Leonid M.Koganov1, Valery A.Liskovets2, Timothy R.S. Walsh3
1Center of Nonlinear Mechanics and Technology Russian Academy of Sciences 117334, Moscow, RUSSIA
2Institute of Mathematics, National Academy of Sciences 220072, Minsk, BELARUS
3Département D’Informatique Université du Québec A Montréal Montréal (Québec), CANADA, H3C 3P8

Abstract

Two combinatorial identities are proved:
(1) \(\quad H_n(\varepsilon) = \frac{n+2}{3} M_n(\varepsilon)\), where \(H_n(\varepsilon)\) denotes the total number of vertices in all the n-edged rooted planar Eulerian maps and \(M_n(\varepsilon)\) denotes the number of such maps.
(2) \(\quad H_n(\mathcal{L}) = \frac{5n^2+13n+2}{2(4n+1)} M_{n }(\mathcal{L})\), where \(H_n(\mathcal{L})\) and \(M_{n}(\mathcal{L})\) are defined similarly for the class \(\mathcal{L}\) of loopless maps.
Simple closed formulae for \(M_n(\varepsilon)\) and \(M_{n}(\mathcal{L})\) are well known, and they correspond to equivalent binomial sum identities.