An Invitation to Analytic Combinatorics

This is the website for the textbook An Invitation to Analytic Combinatorics: From One to Several Variables by Stephen Melczer (Springer Texts & Monographs in Symbolic Computation).

The book manuscript is available here.

The published version of the textbook can be purchased from the publisher’s website and is available for free through many university libraries via Springer Link. For instance, anyone at Waterloo can obtain the published version for free by clicking this link and logging in with their Waterloo account.

A list of known errata can be found here.

Computer Algebra Code for Examples

Each example is encoded as a SageMath Jupyter notebook or Maple worksheet, followed by a static HTML version (which can be viewed on this website, although commands cannot be executed – if you want to run the example yourself make sure to download the code and not the static HTML). An external introduction to SageMath for beginners can run in the browser at this link (or viewed as a static HTML page here).

Some examples (where noted) require the Sage ore_algebra package, the Maple gfun package1, or the Maple Kronecker package. All examples have been tested with Sage 9.2 and Maple 2020.

Run all Sage notebooks interactively in browser using this link.

Chapter 1: Introduction

A zip file with everything for Chapter 1 can be downloaded here.

Example 1.1: Unlabeled Graphs (Sage code)
Example 1.1: Unlabeled Graphs (static HTML)

Example 1.2: The Catalan Generating Function (Sage code)
Example 1.2: The Catalan Generating Function (static HTML)

Chapter 2: Generating Functions and Analytic Combinatorics

A zip file with everything for Chapter 2 can be downloaded here.

Example 2.1: Formal vs. Analytic Power Series (Sage code)
Example 2.1: Formal vs. Analytic Power Series (static HTML)

Example 2.2: Compositions and Partitions (Sage code)
Example 2.2: Compositions and Partitions (static HTML)

Example 2.3: Asymptotics of Surjections (Sage code)
Example 2.3: Asymptotics of Surjections (static HTML)

Example 2.4: Virahanka-Fibonacci Numbers (Sage code)
Example 2.4: Virahanka-Fibonacci Numbers (static HTML)

Example 2.5: Look-and-Say Digit Sequence (Sage code)
Example 2.5: Look-and-Say Digit Sequence (static HTML)

Example 2.6: A Non-N-Rational Series (Sage code)
Example 2.6: A Non-N-Rational Series (static HTML)

Example 2.8: Rooted Binary Trees (Sage code)
Example 2.8: Rooted Binary Trees (static HTML)

Example 2.9: Rooted 3-Ary Trees (Sage code)
Example 2.9: Rooted 3-Ary Trees (static HTML)

Examples 2.8, 2.9, 2.10, and 2.12: Puiseux Expansions for Trees (Maple code)
Examples 2.8, 2.9, 2.10, and 2.12: Puiseux Expansions for Trees (static HTML)

Example 2.16: The Connection Problem for Supertrees (Maple code)
Example 2.16: The Connection Problem for Supertrees (static HTML)

Example 2.17: Kreweras Lattice Walks (Maple code)
Example 2.17: Kreweras Lattice Walks (static HTML)

Example 2.19: Central Binomial Coefficients Squared (Sage code)
Example 2.19: Central Binomial Coefficients Squared (static HTML)

Example 2.20: A Large Solution Space for a Linear Recurrence (Sage code)
Example 2.20: A Large Solution Space for a Linear Recurrence (static HTML)

Example 2.21: Sums of Squares (Sage code)
Example 2.21: Sums of Squares (static HTML)

Example 2.22: A Parametrized Integral (Sage code)
Example 2.22: A Parametrized Integral (static HTML)

Example 2.23: D-Finite and P-Recursive Bases of Solutions (Sage code)
Example 2.23: D-Finite and P-Recursive Bases of Solutions (static HTML)

Examples 2.24 and 2.28: Central Binomial Coefficients Squared (Sage code)
Examples 2.24 and 2.28: Central Binomial Coefficients Squared (static HTML)

Example 2.27: A Numeric Connection Solution (Sage code)
Example 2.27: A Numeric Connection Solution (static HTML)

Example 2.29: Simple Lattice Walks in $\mathbb{N}^2$ (Sage code)
Example 2.29: Simple Lattice Walks in $\mathbb{N}^2$ (static HTML)

Example 2.33: Square-Root Branches (Sage code)
Example 2.33: Square-Root Branches (static HTML)

Example 2.34: Logarithm Branches (Sage code)
Example 2.34: Logarithm Branches (static HTML)

Chapter 3: Multivariate Series and Diagonals

A zip file with everything for Chapter 3 can be downloaded here.

Examples 3.1, 3.3, 3.4: A Simple Binomial Sum (Sage code)
Examples 3.1, 3.3, 3.4: A Simple Binomial Sum (static HTML)

Example 3.9: Reduction to Main Diagonal (Sage code)
Example 3.9: Reduction to Main Diagonal (static HTML)

Example 3.10: The Catalan Generating Function as a Rational Diagonal (Sage code)
Example 3.10: The Catalan Generating Function as a Rational Diagonal (static HTML)

Example 3.11: Counting Leaves in Rooted Plane Trees (Sage code)
Example 3.11: Counting Leaves in Rooted Plane Trees (static HTML)

Example 3.12: Counting Bar Graphs (Sage code)
Example 3.12: Counting Bar Graphs (static HTML)

Example 3.13: Christol’s Open Question (Sage code)
Example 3.13: Christol’s Open Question (static HTML)

Example 3.15: Multivariate Laurent Expansions Depend on Variable Order (Sage code)
Example 3.15: Multivariate Laurent Expansions Depend on Variable Order (static HTML)

Examples 3.16 and 3.22: A Multivariate Walk GF and Constant Term Extraction (Sage code)
Examples 3.16 and 3.22: A Multivariate Walk GF and Constant Term Extraction (static HTML)

Examples 3.17 and 18: A Prototypical Amoeba and Contour (Maple code)
Examples 3.17 and 18: A Prototypical Amoeba and Contour (static HTML)

Example 3.19: Sketching a Contour (Sage code)
Example 3.19: Sketching a Contour (static HTML)

Example 3.21: Diagonals and Multiple Laurent Expansions (Sage code)
Example 3.21: Diagonals and Multiple Laurent Expansions (static HTML)

Example 3.24: Apéry Numbers as Diagonals (Maple code)
Example 3.24: Apéry Numbers as Diagonals (static HTML)

An additional Julia worksheet to plot points in contours can be found here.

Chapter 4: Lattice Path Enumeration, the Kernel Method, and Diagonals

A zip file with everything for Chapter 4 can be downloaded here.

Example 4.1: One Dimensional Excursions (Maple code)
Example 4.1: One Dimensional Excursions (static HTML)

Example 4.2: Dyck Paths and Prefixes (Sage code)
Example 4.2: Dyck Paths and Prefixes (static HTML)

Examples 4.3, 4.5, 4.6+: Short Step Quadrant Models (Sage code)
Examples 4.3, 4.5, 4.6+: Short Step Quadrant Models (static HTML)

Example 4.7: An Infinite Group Model (Sage code)
Example 4.7: An Infinite Group Model (static HTML)

Chapter 5: The Theory of ACSV for Smooth Points

A zip file with everything for Chapter 5 can be downloaded here.

Example 5.3: Smooth Critical Points and the Amoeba Contour (Sage code)
Example 5.3: Smooth Critical Points and the Amoeba Contour (static HTML)

Example 5.8: A Diagonal with No Critical Points (Sage code)
Example 5.8: A Diagonal with No Critical Points (static HTML)

Example 5.13: A Family of Permutations with Restricted Cycles (Sage code)
Example 5.13: A Family of Permutations with Restricted Cycles (static HTML)

The follow notebook covers Exercises 5.1, 5.2, 5.4–5.7, and 5.9–5.12.
Smooth Point Contributions (Sage code)
Smooth Point Contributions (static HTML)

Chapter 6: Lattice Walks and Smooth ACSV

A zip file with everything for Chapter 6 can be downloaded here.

Example 6.1: A Curve of Critical Points (Sage code)
Example 6.1: A Curve of Critical Points (static HTML)

The follow notebook covers Exercises 6.2, 6.3, 6.5, and 6.9.
Highly Symmetric Walk Asymptotics (Sage code)
Highly Symmetric Walk Asymptotics (static HTML)

Chapter 7: Automated Analytic Combinatorics

A zip file with everything for Chapter 7 can be downloaded here.

Example 7.1: Automated Apéry Asymptotics (Maple code)
Example 7.1: Automated Apéry Asymptotics (static HTML)

Example 7.2: A Sequence Alignment Problem (Maple code)
Example 7.2: A Sequence Alignment Problem (static HTML)

Example 7.3: Apéry Revisited (Sage code)
Example 7.3: Apéry Revisited (static HTML)

Example 7.4: Two Critical Points with Positive Coordinates (Sage code)
Example 7.4: Two Critical Points with Positive Coordinates (static HTML)

Example 7.5: A Non-Combinatorial Series Expansion (Sage code)
Example 7.5: A Non-Combinatorial Series Expansion (static HTML)

Example 7.6: Distribution of Leaves in Planar Trees (Sage code)
Example 7.6: Distribution of Leaves in Planar Trees (static HTML)

Examples 7.7–7.10: Computing Critical Points (Sage code)
Examples 7.7–7.10: Computing Critical Points (static HTML)

Chapters 8, 9 and 10

Code in the process of being finalized.


  1. A version of gfun comes built-in to Maple, but better results can often be obtained using the most up-to-date version. The newest version also fixes certain commands which are broken in more recent versions of Maple. ↩︎