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.
Symbolic Method
Loading...
來自 Princeton University 的課程
Analytic Combinatorics
18 個評分
從本節課中
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.
與講師見面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Welcome to Analytic Combinatorics, Part 2.
We're going to dive right into the material today, assuming that everyone
who's watching this has either taken Analytic Combinatorics Part 1 or has
watched the introductory video from analysis of algorithms to analytic
combinatorics that was posted before the class.
today we're going to start right out with ordinary generating functions in the
symbolic method. So a quick overview of what the analytic
combinatorics is. Again it's a calculus for analyzing
properties of large combinatorial structures.
So what we do is use the symbolic method that I'm going to talk about today to
define a class of combinatorial objects along with the notion of size and an
associated generating function and then we use standard operations, or
combinatorial constructions to develop a specification of the structure.
And the result is[UNKNOWN] via the symbolic method, a direct derivation of a
equation that has to be satisfied by the generating function, either an implicit
or an explicit equation. and then the classic next steps are to
extract coefficients and use classic asymptotics to estimate them.
And eventually get asymptotic estimates that quantify the desired properties.
this general approach is what we covered in part one, and is covered in our second
edition of our book Introduction to analysis of algorithms.
for part two we're going to talk about the symbolic method in more detail and
many other examples. but when it comes to estimating the
asymptotic values of the coefficient, we're going to use complex asymptotics.
We don't have to find an explicit solution and that'll be the second part
of this part two, where we'll talk about directly deriving asymptotic estimates
that give us the desired properties. and that's what the Analytic
Combinatorics book is all about. First part's about the symbolic method.
Second parts about asym deriving directly asymptotic estimates of, of the
coefficients. so the overview is a bit like this.
These are the eight chapters that we're going to talk about.
the symbolic method there are three chapters, ordinary generating functions,
exponential, and multi-various. and then some chapters on complex
analysis. and the idea's that when we have the
specification, we start with the specification, then symbolic method is
the process that gives us a generating function equation.
and complex asymptotics gives us another set of processes that immediately give us
the asymptotic estimates that are our desired result.
so today we're going to talk just about the symbolic method and for the next
couple of lectures. and again, there's some easier examples
that moves a bit slower in part 1 and in analysis of algorithms in the purple
book, Analytic Combinatorics, has a very rigorous treatment.
this lecture is somewhat in between, it's an overview that assumes some familiarity
with generating functions and basic mathematics; like, like it's covered in
part 1 of this course. If you move, find that we're moving a bit
quickly refer back to Analysis of Algorithms book.
[COUGH] . If you find that we're moving a bit
slowly read chapters one, two, and three of Analytic Combinatorics.
And then within a lecture or two we'll all be moving at the same pace, I think.
So basic definitions. A combinatorial class is a set of
combinatorial objects and an associated size function.
That's our starting point that's our object of study.
in the, today what were going to talk about is a, as a primary object of study,
the ordinary generating function associated with the class.
And that's a formal power series, where you have a variable c and use some for
all objects in the class z the to size of that object, that's the ordinary
generating function. So the size function is like an absolute
value just says that's like the size of the object.
[COUGH]. And then the class name, the class name
is usually a capital letter with the same letter as the generating function.
and then the object name is usually a lower case letter of the same letter.
[COUGH]. Now there's a very elementer elementary
identity that's fundamental to all the manipulations of the symbolic method.
And that is, this generating function where we look at all the objects, raise z
to the size of the object. that's equal to summing for all n the
number objects of size n times z to the end.
because if there's A sub N objects size N, then there's A sub N terms on that
left hand side one for each object of size N and collect them together you get
A sub N Z to the N. And that's a fundamental identity that
we're going to work with. And our goal is to find good estimates of
this value A sub N. And we refer to that as with the notation
square brackets Z to the N, that means the coefficient of Z to the N in A of z,
that's A sub N. and again I mention the conventions,
usually we try to use a roman letter for the class name.
for the generating function name, it's the same letter with an argument.
Uh,[COUGH] for in the book we use a slightly different font.
object variable is just lower case of the same letter and then the coefficient is
subscripted of the same letter. Uh,[COUGH] and size we usually use
capital N or little N and this kind of adopts a fantasy that we have a different
letter for each class but actually there's only 26 letters.
And we look at way way more classes, so sometimes we have a conflicts in these
names. but we do the best we can.
Now so with the symbolic method, what we can do is specify the class and at the
same time characterize the generating function.
that's the process that we want to talk about today.
Uh,[COUGH] so there's a number of basic combinatorial objects that are
characterized well by ordinary generating functions and they're called unlabeled
classes, and we'll talk about that distinction later.
so integers or strings which are sequences of characters, recursive
structures, trees, languages. and then compositions and partitions
which are compositions are positive integers sum to add, and partitions are
unordered compositions and we'll look at all of those soon.
so, to describe those communotorial classes, we use basic operations or
constructions. so if we have two classes A and B of
unlabeled objects, and again we'll talk about what that means later on, that have
the generating functions A of Z and B of Z, then we can perform some natural
operations on them so the disjoint union is just take object from A and an object
from B. And be uh,[COUGH] that makes a new class
and the ordinary generating function of that class is just sum the two generating
functions. and then there's a Cartesian product if
we take a pair of copies, one from A, one from B, then we get a class whose already
generating functions, the product of the two generated functions.
And the proofs of these are easier, we'll look at them in just a second.
And then there's sequence which is applied the product multiple times taken
either none or one or pairs or triples any sequence of objects from a class,
then you get another class whose generating function 1 over 1 minus A of
z. Those are, with those basic constructions
we can describe quite a rich set of combinatorial classes but we also have
many other constructions and we'll look at some today.
Uh,[COUGH] so here's just the proofs about the generating functions.
so for A plus B, if you have an object that belongs to either A or B and you sum
over all objects in A plus B. Then you can split the sum into two
parts: the ones from A and the ones from B, then, by definition then, that gives
you the sum of the two generating functions.
for cartesian product, it's slightly more complicated but not much.
if you take an ordered pair of objects from a be all ordered pairs and you sum
over all ordered pairs then you can treat that as a convolution of two sums.
and since there's one from A and one from B and we're combining them, then the
object that's the ordered pair, the size of that object, is the sum of the sizes
of the two objects that we combine. and those are independent, so we can just
split those sums and get the product. so the generating function for the
Cartesian product is the product of the generating functions.
and for sequence well [COUGH], if you take a sequence of size k, then just
extending the product operation, you get A of Z to the K.
and sequence is 0 plus 1 plus so forth,[INAUDIBLE] actually for any
seqence of integers and so if you take any size, it's just 1 plus A of Z plus A
of Z squared and so forth, which is just 1 over 1 minus A of Z.
so that's the correspondences for the basic operations that show that if we
apply one of these operations, then we immediately imply a relationship on the
generating function. and again if you find this proof a bit
confusing and you want to see some more basic examples please take a look at
chapter five of our Introduction to Analysis of Algorithms book.
We're in part one of the Analytic Combinatorics course.
[COUGH] so that's a quick introduction to the symbolic method.
