Singularity Analysis of Generating Functions

1990/05/01 by Philippe Flajolet, Andrew Odlyzko · 44 citations
Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Mathematical functions and polynomials

paper · doi:10.1137/0403019

openalex publication_date 1990/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

This work presents a class of methods by which one can translate, on a term-by-term basis, an asymptotic expansion of a function around a dominant singularity into a corresponding asymptotic expansion for the Taylor coefficients of the function. This approach is based on contour integration using Cauchy’s formula and Hankel-like contours. It constitutes an alternative to either Darboux’s method or Tauberian theorems that appears to be well suited to combinatorial enumerations, and a few applications in this area are outlined.

Citations

• Combinatorial Enumeration

Cited by

• Tractable Model for Tunable Non-Markovian Dynamics
• Nonlinear instability of rolls in the 2-dimensional generalized Swift-Hohenberg equation
• Near-Light-Cone Nonhydrodynamic Structure from Boosted Hydrodynamics
• On the Betti numbers, Poincaré polynomials, and Euler characteristics of \mathcal M_0,n
• Asymptotic expansions for factorial moments of some distributions in the analysis of algorithms
• Transversal structures on triangulations: a combinatorial study and straight-line drawings
• Analytic urns
• Twenty combinatorial examples of asymptotics derived from multivariate\n generating functions
• Asymptotics of Multivariate Sequences, part I. Smooth points of the singular variety
• Complexity Analysis of Vario-eta through Structure
• Walks on the slit plane
• Many 2-level polytopes from matroids
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• The degree profile of Pólya trees
• Asymptotic distribution of motifs in a stochastic context-free grammar\n model of RNA folding
• Combinatoire du polynôme de Tutte et des cartes planaires
• Heavy-traffic Asymptotics of Priority Polling System with Threshold Service Policy
• Spanning tree size in random binary search trees
• Irreducible compositions and the first return to the origin of a random walk
• Griffiths phase emerging from strong mutualistic disorder in high-dimensional interacting systems
• Finding Efficient Recursions for Risk Aggregation by Computer Algebra
• Delange's Tauberian theorem and asymptotic normality of random ordered factorizations of integers
• On the zeros of the Riemann Zeta function
• Combinatorics of locally optimal RNA secondary structures
• Explicit formula for the generating series of diagonal 3D rook paths
• Steady state clusters and the Rath-Toth mean field forest fire model
• The generalized weighted probability measure on the symmetric group and\n the asymptotic behavior of the cycles
• Asymptotics of the transition probabilities of the simple random walk on self-similar graphs
• Psi-series method in random trees and moments of high orders
• Limits of biconditioned Bienayme-Galton-Watson trees
• Asymptotic connectivity for the network of RNA secondary structures
• Branching Brownian motion with selection
• Retakh's Motzkin paths and some combinatorial comments
• Counting d-polytopes with d+3 vertices
• Asymptotic Enumeration of Non-crossing Partitions on Surfaces
• Conservation of Singularities in Functional Equations Associated to Collatz-Type Dynamical Systems; or, Dreamcatchers for Hydra Maps
• Additive functionals on random search trees
• XML Compression via DAGs
• Expected number of pattern and submap occurrences in random planar maps
• Numerical stability of Grünwald-Letnikov method for time fractional delay differential equations
• On asymptotics, Stirling numbers, Gamma function and polylogs
• On spectral properties of the Schreier graphs of the Thompson group F
• Scaling limit of boundary random walks: A martingale problem approach
• Complete left tail asymptotic for supercritical multitype branching processes

Related

• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
• Singularity analysis, Hadamard products, and tree recurrences
• A constructive elementary method for local resolution of singularities
• Analysis of series expansions for non-algebraic singularities
• Resolution of singularities, asymptotic expansions of oscillatory integrals, and related phenomena