Analytic combinatorics is a calculus (set of mathematical tools) for analyzing properties of large combinatorial structures.

Book website of book videocourse

Symbolic method

• Define a combinatorial class:
  • Define a class of combinatorial objects
  • Define a notion of size (and an associated generating function)
• Use standard operations to develop a specification of the structure

Result: A direct derivation of a GF equation (implicit of explicit), i.e. an equation that the Generating function must satisfy.

Classic next steps:

• Extract coefficients
• Use classic asymptotics to estimate coefficients

Result: Asymptotic estimates that quantify the desired properties.

Symbolic method for unlabelled structures (Ordinary generating function)

Symbolic method for labelled structures (Exponential generating function)

Video course

Analytic Combinatorics, Part II (Analytic Combinatorics)

In Coursera: Analytic Combinatorics

Applications: Analysis of algorithms, Random deterministic automata, ...

Enumerative combinatorics of maps