Exercises

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

18 notes

Princeton University

Analytic Combinatorics

18 notes

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.

À partir de la leçon

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.

Symbolic Method11:23

Trees and Strings 14:22

Powersets and Multisets 13:00

Compositions and Partitions 15:02

Substitution 6:22

Rencontrer les enseignants

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

Alright, let's finish with a few exercises.

now in the Analytic Combinatorics books the exercises are not all framed in the

form of a question. they are framed in the form of

information for of interest for interesting applications, something that

might be pursued further. so when you address those kind a keep

that in mind. What you're suppose to do maybe is fill

in the missing steps. so this is the one that shows a a very

typical applications of analytic combinatorics for coding.

so very often you have a structure encoded in some way.

And you want to know how many bits you need to encode that structure.

and this exercise talks about how analytic combinatorics can help us figure

that out for some application of interest.

and the second exercise to take a look at 1.43 points out that as I was mentioning.

once you have the generating function derived through the symbolic method you

can use that to get information about the quantities of interest by computing with

the recurrence. so this is an exercise that that has you

take a look at that. so as assignments related to this lecture

go ahead and read Chapter 1 in the text. again, it goes into much, much more

detail than we have time for going into lecture.

And it's not expected that everyone understands everything on every page.

It's way too much in there for that. but there's definitely worthwhile to

spend some time with every page for sure. and then the good exercise to write up

solutions to those two exercises I just mentioned.

and then programming exercises that people might find interesting.

first one is what, what coin should the government issue to maximize the number

of ways to change the dollar. let's say that's our goal.

so, and, and you probably have to write a program to do that use Pully's/g method.

or, and another interesting program is the solution to that exercise.

It gives a way to estimate the rate of growth of the Cayley numbers or the

partition numbers by just taking the ratio of h sub over h sub n minus 1.

Or p sub n over p sub n minus 1. and so easy to write programs to do that.

that's a worthwhile exercise. That's an introduction to ordinary

generating functions for in specifying combinatorial structures at the same

time.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play