Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

Asymptotic enumeration of orientations

Stefan Felsner, Eric Fusy, Marc Noy


We find the asymptotic number of 2-orientations of quadrangulations with n inner faces, and of 3- orientations of triangulations with n inner vertices. We also find the asymptotic number of prime 2-orientations (no separating quadrangle) and prime 3-orientations (no separating triangle). The estimates we find are of the form c n^(-\alpha) \gamma^ n, for suitable constants c, \alpha, \gamma, with \alpha = 4 for 2-orientations and \alpha = 5 for 3-orientations. The proofs are based on singularity analysis of D-finite generating functions, using the Fuchsian theory of complex linear differential equations.

Full Text: PDF PostScript