On the enumeration of planar Eulerian orientations

Claire Pennarun
University of Bordeaux

Nicolas Bonichon
University of Bordeaux

Mireille Bousquet-M\'elou
CNRS, University of Bordeaux

Paul Dorbec
University of Bordeaux

PDF

Minisymposium: COMBINATORICS

Content: Eulerian planar maps are planar maps with all vertices of even degree. The number of Eulerian planar maps with a fixed number of edges $m$ is well known, and they are in bijection with many combinatorial families, such as balanced Eulerian trees or bi-cubic maps. Planar Eulerian orientations are directed planar maps in which the in- and out-degrees of every vertex are equal. We first count the number of planar Eulerian orientations for $m \leq 12$ ($m$ is the number of edges) thanks to an encoding based on bilateral Dyck words. The values found (2, 10, 66, 504, 4216, 37548...) do not match with any known series from the OEIS. We then present a sequence of algebraic series giving lower and upper bounds of the growth rate of planar Eulerian orientations. We show in particular that the growth rate of planar Eulerian orientations is between $10.69^m$ and $12.94^m$.

Back to all abstracts