Princeton University

Analytic Combinatorics

Taught in English

Some content may not be translated

22,793 already enrolled

Course

Gain insight into a topic and learn the fundamentals

Robert Sedgewick

Instructor: Robert Sedgewick

4.6

(62 reviews)

Intermediate level
Some related experience required
16 hours to complete
3 weeks at 5 hours a week
Flexible schedule
Learn at your own pace

Details to know

Assessments

8 quizzes

See how employees at top companies are mastering in-demand skills

Placeholder

There are 8 modules in this course

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.

What's included

7 videos2 readings1 quiz1 discussion prompt

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.

What's included

7 videos1 reading1 quiz1 discussion prompt

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.

What's included

5 videos1 reading1 quiz1 discussion prompt

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.

What's included

6 videos1 reading1 quiz1 discussion prompt

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.

What's included

6 videos1 reading1 quiz1 discussion prompt

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.

What's included

5 videos1 reading1 quiz1 discussion prompt

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.

What's included

6 videos1 reading1 quiz1 discussion prompt

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.

What's included

5 videos1 quiz

Instructor

Instructor ratings
5.0 (16 ratings)
Robert Sedgewick
Princeton University
7 Courses1,697,224 learners

Offered by

Recommended if you're interested in Math and Logic

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 62

4.6

62 reviews

  • 5 stars

    79.03%

  • 4 stars

    12.90%

  • 3 stars

    3.22%

  • 2 stars

    1.61%

  • 1 star

    3.22%

AN
4

Reviewed on Feb 15, 2020

ZH
5

Reviewed on Aug 10, 2020

Placeholder

Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions