Exercises

Loading...

Analytic Combinatorics

4.7 (26 ratings) | 13K Students Enrolled

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.

View Syllabus

Reviews

4.7 (26 ratings)

5 stars
22 ratings
4 stars
2 ratings
3 stars
1 ratings
2 stars
1 ratings

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.

Roadmap13:38

Complex Functions 13:14

Rational Functions 19:23

Analytic Functions and Complex Integration 23:56

Meromorphic Functions 34:55

Exercises 3:24

Taught By

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

Transcript

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.