Summary

Loading...

Do curso por Princeton University

Analytic Combinatorics

23 classificações

Princeton University

Analytic Combinatorics

23 classificações

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.

Na lição

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.

Symbolic Method for Labelled Classes 18:36

Words and Strings 12:21

Labelled trees 15:25

Conheça os instrutores

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

Now let's finish up with a quick summary of the things that we've covered in this

lecture. the main topic has been the symbolic

method for labelled classes, and particularly the transfer theorem shows

how the constructions that we consider transfer to operations on generating

functions. So we consider the disjoint union

operation. And the main one, which is the labelled

product operation, where we, we relabel objects in all possible ways.

And we would get a product on the generating function, sequences of length

k, which we would generate in function a to the z to the k, sequence of any length

1 over 1 minus. Same with sets of length k or sets of any

size, and cycles of length k or cycles of any size.

And there's many others that people have defined, like the box product which has a

corresponding operation on the generating function.

with these basic operations and just a few examples, there's many, many other

examples in the book. we were able to define a whole host of

commonatorial classes. all with a relatively simple description

and then leading to Directly from the transfer theorem to exponential equations

that exponential generating functions have to satisfy.

And we have variations on these to lead to a, a huge variety of different common

notarial classes and still have a specific equation that the generating

functions have to satisfy. That fits with our overview to analyze

properties of a large combinatorial structures, we use the symbolic method to

get directly generating function equation.

now its, important to note that the equations that we get vary widely in

nature. Some of them are quite simple, some of

them are quite complicated. but those are the generating functions of

the counting sequences that we seek. so in the second part where we derive

asymptotics from generating functions, we're also going to need general tools

that can handle all of these different types, of generating functions.

But still, the derivations that give us the generating functions, were all,

really, essentially, quite simple. in fact to the point where again this

brings in also unlabeled classes. We we can automate the transfer from

specifications to generating functions. and in fact Philippe and, and his

students Bruno Salvy and Paul Zimmerman did so in the 90's.

in much of this work is reflected in modern symbol manipulation systems.

Another thing we can do is use specs to generate huge random structures.

one easy approach is to just take the spec and use a recursive program that is

based on the spec. and that's okay but it doesn't get you

really large structures because it takes quadratic time.

but there is a probabilistic method that gets for a given size, that gets a random

structure of, approximately, that size and works in linear time.

And this is, becomes, increasingly important, for checking, whether a

combinatorial model that someone might have of the real world, actually matches

with observed in the real world. Can generate, a large number of random

structures and check if they're properties correspond to the real world

thing, object that's being studied. whether it be a DNA sequence or a

computer network or whatever else you've found that people are studying nowadays.

so that's called Bolton sampling in that's reference for for that as well.

but I think again it's all about the utility of generating functions.

and really the bottom like is that Without something like the symbolic

method or generating functions. people were doing really horrendously

detailed and difficult calculations. and this approach really does eliminate

virtually all of them. That's the summary of the symbolic method

both for labelled and unlabelled methods.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play