Asymptotic enumeration of orientations

作者：Felsner Stefan^*; Fusy Eric; Noy Marc

来源：Discrete Mathematics and Theoretical Computer Science, 2010, 12(2): 249-262.

• Orientation
• Quadrangulation
• Triangulation
• D-finite generating function

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.

• 出版日期2010