To support our site, Class Central may be compensated by some course providers.

Analytic Combinatorics

Princeton University via Coursera

students interested
  • Provider Coursera
  • Subject Calculus
  • $ Cost Free Online Course (Audit)
  • Session Upcoming
  • Language English
  • Effort 6-8 hours a week
  • Start Date
  • Duration 8 weeks long

Taken this course? Share your experience with other students. Write review

Overview

Sign up to Coursera courses for free Learn how

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.

Syllabus

Combinatorial Structures and OGFs
Our first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.

Labelled Structures and EGFs
This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.

Combinatorial Parameters and MGFs
This lecture describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail.

Complex Analysis, Rational and Meromorphic Asymptotics
This week we introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required.

Applications of Rational and Meromorphic Asymptotics
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.

Singularity Analysis
This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity, approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term.

Applications of Singularity Analysis
We see how the Flajolet-Odlyzko approach leads to universal laws covering combinatorial classes built with the set, multiset, and recursive sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in Lectures 1 and 2.

Saddle Point Asymptotics
We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2.

Taught by

Robert Sedgewick

Help Center

Most commonly asked questions about Coursera Coursera

Reviews for Coursera's Analytic Combinatorics
4.0 Based on 2 reviews

  • 5 star 50%
  • 4 star 0%
  • 3 star 50%
  • 2 star 0%
  • 1 star 0%

Did you take this course? Share your experience with other students.

Write a review
  • 1
Anonymous
3.0 3 years ago
Anonymous completed this course.
This course is very hard but its a really beautiful and interesting subject. Pr Sedgewick really knows what he talks about.

It looks like there are prior courses that would make it easier to access this material, but I took the course without attending those, and despite my rather good background, i fought a lot with the new notations early in the course. I had wished Pr Sedgewick spent more time on a few precise examples , for example when explaining the cycle construction, or the star product.

The problem of this course, is that it focuses too much on its powerful r…
4 people found
this review helpful
Was this review helpful to you? Yes
Marat M
5.0 4 years ago
by Marat partially completed this course, spending 10 hours a week on it and found the course difficulty to be very hard.
Was this review helpful to you? Yes
  • 1

Class Central

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free

Never stop learning Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.