Course Materials

This page provides access to various materials for use in teaching and learning from the book Analytic Combinatorics including lecture slides, a sample schedule, assignments, and exams. Along with a MOOC or certificate course (see tabs at bottom left), it is appropriate for use by instructors as the basis for a "flipped" class on the subject, or for self-study by individuals.

Each lecture corresponds to a chapter in Analytic Combinatorics, so everyone is encouraged to study the corresponding chapter in conjunction with the lectures. If you view a lecture, you just spend an hour with the material; if you study the lecture slides and solve the assigned problems, you might spend several hours; if you dive into a topic by careful study of the book itself, you might find your self enjoying at least another order of magnitude of engagement with the material.

Flipped Class.

If you are an an instructor teaching analytic combinatorics, an effective way for you to teach the material in a typical college class is to adhere to a weekly cadence, as follows: Important note:A common mistake in teaching a flipped class is to add too much enrichment material. Our experience is that time in class meetings is much better spent preparing students for success on problem sets and exams. If an instructor makes it clear that the best way to prepare for exams is to watch the lectures and do the reading, most students will do so. Class meetings then can involve interacting with students and with the material in such a way as to reinforce understanding. For example, having students prepare and discuss potential exam questions is an excellent activity. You can find some guidelines and examples at right in the table below.

Self-study.

An effective way to learn the material on your own is to play the lectures on some regular schedule, do the associated reading, and attempt to solve some of the assigned exercises on your own. If you get stuck on a particular exercise, find some others in the book or on this website, or try to solve some of the problems given in the lectures without looking at the solutions there. In the future, we plan to add more exercises with solutions to this website, but that is work in progress.

While some of the reading material may be difficult for a typical undergraduate to master on such a quick pass through, a substantial fraction of the coverage is elementary, and the lectures provide a firm basis for understanding the key concepts.

Princeton students.

At Princeton, we use these materials to teach the second half of our senior-level undergraduate course An Introduction to Analytic Combinatorics (the first half of the course is on the Analysis of Algorithms booksite). Click on the COS 488 tab on the sidebar for logistical details. We update the material as the semester progresses. You can look ahead in the table below to get an idea of what is to come, but assignments are not "official" until you receive them by e-mail.



WEEKLY ASSIGNMENT LECTURE VIDEOS LECTURE SLIDES Q&A
ACweek1.txt

Note I.23

Note II.11

  0. Random Sampling

    0.1 Basics

    0.2 Achieving uniformity

    0.3 Rejection

    0.4 Recursive method

    0.5 Analytic samplers

  1. Combinatorial Structures/OGFs

    1.1 Symbolic method

    1.2 Trees and strings

    1.3 Powersets and multisets

    1.4 Compositions and partitions

    1.5 Substitution

  2. Labelled Structures/EGFs

    2.1 Basics

    2.2 Symbolic method (labelled)

    2.3 Words and strings

    2.4 Labelled trees

    2.5 Mappings

    2.6 Summary

AC00-Random.pdf

AC01-OGFs.pdf

AC02-EGFs.pdf

Guidelines

ACqa1.pdf

ACweek2.txt

Note III.17

Web Exercise III.3

  3. Combinatorial Parameters/MGFs

    3.1 Basics

    3.2 Moment calculations

    3.3 OBGF examples

    3.4 Labelled classes

AC03-MGFs.pdf

ACqa2.pdf
ACweek3.txt

Web Exercise IV.2

Note IV.28

Program IV.2

  4. Complex Analysis, Rational and Meromorphic Asymptotics

    4.1 Roadmap

    4.2 Complex functions

    4.3 Rational functions

    4.4 Analytic functions/complex integration

    4.5 Meromorphic functions

AC04-Poles.pdf ACqa3.pdf
ACweek4.txt

Web Exercise V.1

Web Exercise V.2

Web Exercise V.5

  5. Applications of Rational and Meromorphic Asymptotics

    5.1 Bitstrings

    5.2 Other familiar examples

    5.3 Compositions

    5.4 Supercritical sequence schema

    5.5 Summary

AC05-PoleApps.pdf

ACqa4.pdf
ACweek5.txt

Web Exercise VI.1

Web Exercise VI.2

Web Exercise VII.1

  6. Singularity Analysis

    6.1 Prelude

    6.2 Standard function scale

    6.3 Singularity analysis

    6.4 Schemas and transfer theorems

  7. Applications of Singularity Analysis

    7.1 Simple varieties of trees

    7.2 Labelled sets

    7.3 Mappings

    7.4 Tree-like classes

    7.5 Summary

AC06-SA.pdf

AC07-SAapps.pdf

ACqa5.pdf
ACweek6.txt

  8. Saddle-Point Asymptotics

    8.1 Modulus surfaces

    8.2 Saddle point bounds

    8.3 Saddle point asymptotics

    8.4 Applications

    8.5 AC wrapup

AC08-Saddle.pdf

ACqa6.pdf

Review Problem Set

WE I.2

WE II.2

WE III.8

WE IV.5

WE V.7

WE VI.3

WE VII.4