Exercises

Loading...

From the course by Princeton University

Analytic Combinatorics

19 ratings

Princeton University

Analytic Combinatorics

19 ratings

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. All the features of this course are available for free. It does not offer a certificate upon completion.

From the lesson

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.

Complex Functions 13:14

Rational Functions 19:23

Analytic Functions and Complex Integration 23:56

Meromorphic Functions 34:55

Meet the Instructors

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

We'll just finish up with a couple of exercises that people might do to check

their understanding of this lecture. this one is a note from the book where it

talks about using these techniques to enumerate what's called a Super Necklace

which is labelled cycle of cycles. and you can look in the book for a

definition of that and see how the symbolic transfer gives this generating

function. and the problem is to show that that's

asymptotic to 1 over n times 1 minus 1 over e to the minus n.

so and there's a hint take derivatives. so that's we'll do lots more applications

of the meromorphic transfer theorem later on.

And then this is just an exercise on a different kind of combinatorial object.

so, again, the best thing to do, particularilly for people without much

familiarity with complex analysis is to review the lecture in the lecture notes

and also to look at the book in the section on complex analysis.

As usual, there is much much more in the book than I have a chance to talk about

in lecture. So your best strategy for now is to try

to get a feeling for what's there, pursue what you find interesting but you're not

going to be able to understand every detail without putting in many, many

hours. it's, our, our, our goal is to give you

some familiarity with the major concepts and give you a place to research later on

when you discover problems that you know, analytic combinatorics might be effective

for. and go ahead and write up a solution to

that note. and then also, I'd urge people to do

these simple programming exercises just to connect the abstractions that I've

talked about a little bit closer to the real world.

So, one thing you can do is compute the percentage of permutations say, that have

no singleton or doubleton cycles. and you can make a recurrence to go ahead

and compute that. And then compare it with the asymptotic

estimate that we get from the analytic combinatorial, save for n equals 10 and

and 20. another thing you do is get like code on

the book's site for plotting complex numbers on a greyscale image according to

the absolute value. And and, and plot the function associated

with that in a Super Necklace, just or plot some other function that you find

interesting. just to see how easy it is to create

these kinds of images. because we're going to be them to gain

intuition about the kind of functions that we talk about later on.

so, again next time we'll look at, lots, lots, lots and lots more applications of,

of, this basic transfer theorem.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play