Math 2.0

Combinatorics Definition

Analytic combinatorics

Builds on Generating functionRadius of convergenceAnalytic functionEnumerative combinatorics

Definition

Let (an)n≥0(a_n)_{n \ge 0} be a sequence of counts with generating function A(z)=∑nanznA(z) = \sum_{n} a_n z^n or ∑nanzn/n!\sum_n a_n z^n / n!. Analytic combinatorics is the branch of enumerative combinatorics that derives the asymptotic behaviour of ana_n as n→∞n \to \infty from AA. Here AA is viewed as an analytic function of a complex variable zz. Its main methods are:

  1. location of the dominant singularities, which fixes the exponential growth rate;
  2. singularity analysis, which transfers the local behaviour of AA near a dominant singularity to the coefficients;
  3. saddle-point estimates of the Cauchy coefficient integral, mainly for entire functions AA.

Remarks

The basic principle is the Cauchy–Hadamard formula. If AA has radius of convergence ρ\rho with 0<ρ<∞0 < \rho < \infty, then lim sup⁡n→∞∣an∣1/n=1/ρ\limsup_{n \to \infty} \abs{a_n}^{1/n} = 1/\rho. When an≥0a_n \ge 0, Pringsheim's theorem says that z=ρz = \rho is itself a singularity of AA.

Example: the Catalan generating function is C(z)=1−1−4z2zC(z) = \frac{1 - \sqrt{1 - 4z}}{2z}. Its dominant singularity is z=1/4z = 1/4, where CC behaves like 2−21−4z2 - 2\sqrt{1 - 4z}. Singularity analysis then gives Cn∼4nπ n3/2C_n \sim \frac{4^n}{\sqrt{\pi}\, n^{3/2}}.

Non-example: a proof that (2nn)≤4n\binom{2n}{n} \le 4^n by counting subsets is not analytic combinatorics. It uses no property of a generating function as a function of a complex variable.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Analytic function, concept, no evidence levelAnalytic functionconceptEnumerative combinatorics, concept, no evidence levelEnumerative combinato…conceptGenerating function, concept, no evidence levelGenerating functionconceptRadius of convergence, concept, no evidence levelRadius of convergenceconceptAnalytic combinatorics, definition, no evidence levelAnalytic combinatoricsdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Analytic function concept
  2. Enumerative combinatorics concept
  3. Generating function concept
  4. Radius of convergence concept
  5. Analytic combinatorics definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Analytic_combinatorics
About this page
TagXGZ2YYCNWK
URIm2://XGZ2YYCNWK
Kinddefinition
WritingW0 stub
MSC05A16, 05A15, 30B10
DefinesAnalytic combinatorics
UsesGenerating function, Radius of convergence, Analytic function, Enumerative combinatorics
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.