Summary

Loading...

Do curso por Princeton University

Analytic Combinatorics

16 ratings

Princeton University

Analytic Combinatorics

16 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.

Na lição

Applications of Singularity Analysis

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.

Simple Varieties of Trees16:01

Labelled Sets 15:37

Tree-like Classes 16:47

Conheça os instrutores

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

Just to summarize we've looked at many different applications of singularity

analysis starting with some familiar ones rooted ordered trees and binary trees.

we looked at the unary-binary trees and Cayley trees always getting generating

function by the symbolic method and coefficient asymptotics.

By a transfer theorem built from singularity analysis.

we looked at properties of mappings. 2-regular graphs, labeled a higher piece,

and other implicit, tree-like classes, and always being able to go from

construction to generating function to coefficient asymptotics.

And these are only representative examples for each one of them, and

there's many, many other types of classes that are similar that we can define and

still get immediately to the coefficient asymptotics.

we have a very powerful and general calculus for deriving estimates of, of

coefficients from combinatorial constructions.

if you can specify it, you can analyze it.

Singularity analysis is a very effective approach.

For generating function equations for classes with the GFs that are not.

It actually, that are not meromorphic. It actually also works for meromorphic

functions it's, it's more general. And some of these schemas that we've

actually done were meromorphic. Though we didn't, we just didn't we just

didn't talk about it. Could be.

so the idea is that what, we have these schema that can unify the analysis for

entire families of classes. we talked about the x blog, and simple

variety of trees, and the context free classes last time, and we didn't show any

applications this time, in implicit tree like classes, and we can always get out

to the a coefficient asymptotics for large families of combinatorial classes.

and there's other schema also that have been proven.

Now, not every example goes as smoothly as the ones that I've shown in lecture.

and particularly for context free and related classes the calculations involved

to actually find the specific constant can be complicated.

but usually it could be mechanized and it's reasonable to expect for a great

variety of classes that you're going to find this kind of behavior just using the

basic principle of coefficient asymptotics is the location of the

singularity is going to give you the asymptotic growth and the nature of the

singularity is going to tell you about the sub-exponential factor in the

constant. And in a great many cases we can compute

these things exactly into arbitrary asymptotic accuracy.

so next lecture we're going to talk about what to do with generating functions that

have no singularities. but, singularity analysis is really at

the heart of analytic combinatorics.

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.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play