×

zbMATH — the first resource for mathematics

Total vertex enumeration in rooted planar maps. (English) Zbl 0993.05087
The authors prove that the total number of vertices in all rooted planar Eulerian maps with \(n\) edges is \((n+2)/3\) times the number of such maps. They prove also an analogous relation, with the coefficient \((5n^2+13n+2)/(8n+2)\), for rooted planar loopless maps. (Simple formulas for numbers of these maps are well known.) Two different proofs for both classes of maps are given, one by Lagrange inversion and the other binomial. To find a direct proof of these combinatorial identities is posed as a problem.

MSC:
05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05A19 Combinatorial identities, bijective combinatorics
PDF BibTeX XML Cite