

A179299


Coefficients of power series enumerating pentagulations, dangulations of girth 5.


1




OFFSET

0,2


COMMENTS

Bernardi, p.10. A dangulation is a planar map with faces of degree d. We present for each integer d => 3 a bijection between the class of dangulations of girth~d and a class of decorated plane trees. Each of the bijections is obtained by specializing a "master bijection" which extends an earlier construction of the first author. Bijections already existed for triangulations ($d=3$) and for quadrangulations (d=4). As a matter of fact, our construction unifies a bijection by Fusy, Poulalhon and Schaeffer for triangulations and a bijection by Schaeffer for quadrangulations.
For d => 5, both the bijections and the enumerative results are new. We also extend our bijections so as to enumerate pgonal dangulations, that is, dangulations with a simple boundary of length p. We thereby recover bijectively the results of Brown for pgonal triangulations and quadrangulations and establish new results for d => 5. A key ingredient in our proofs is a class of orientations characterizing dangulations of girth d. Earlier results by Schnyder and by De Fraisseyx and Ossona de Mendez showed that triangulations of girth 3 and quadrangulations of girth 4 are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. We extend this characterization by showing that a dangulation has girth $d$ if and only if the graph obtained by duplicating each edge $d2$ times admits an orientation having indegree d at each inner vertex.


LINKS

Table of n, a(n) for n=0..4.
Olivier Bernardi, Éric Fusy, A bijection for triangulations, quadrangulations, pentagulations, etc, arXiv:1007.1292 [math.CO], 20102011.
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s314 (1964) 746768.
W. G. Brown. Enumeration of quadrangular dissections of the disk, Canad. J. Math., 17 (1965) 302317.
W. T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249271.


EXAMPLE

For d = 5 the series starts as F(x) = x + 5 x^3 + 121 x^5 + 4690 x^7 + 228065 x^9 + ...


CROSSREFS

Sequence in context: A028448 A108791 A282271 * A012179 A012026 A012190
Adjacent sequences: A179296 A179297 A179298 * A179300 A179301 A179302


KEYWORD

nonn


AUTHOR

Jonathan Vos Post, Jul 09 2010


STATUS

approved



