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.
Trees and Strings
Loading...
来自 Princeton University 的课程
Analytic Combinatorics
23 个评分
从本节课中
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
as an introduction to the use of the symbolic method to describe combinatorial
classes while of the same time getting a generating function equations for the
generating functions of those classes. we'll look at trees and strings which,
provide rich set of examples as the way. from the elementary to some of the most
challenging combinatorial problems that have been studied.
so the classic example of the symbolic method is trees.
So how many trees are in there with N nodes?
where a tree is described recursively as a tree.
These are ordered, rooted trees. So it's a node connected to a sequence of
trees. and so these are the small values,
there's five different trees five nodes. And these two trees are different because
the order is significant and, and so forth.
So these are the familiar catalan numbers.
and with a symbolic method we can immediately drive the generating function
for the catalan numbers. so here's how it goes.
So we, we define the class of all trees to be G and then the construction using
the basic operations, we say a tree is a node in a sequence of trees.
it's as simple as that and just using the transfer theorem from the construction to
the generating function that we just described.
That immediately says that the generating function has to satisfy the equation z
for the node over 1 minus G of z for the sequence of trees.
G of z equals z times z over 1 minus G of z.
in solving that G of z minus G of z squared equals z, so that's an equation
that the generating function must satisfy that we get immediately from the
combinatorial construction direct transfer.
now we can solve this one in particular using the quadratic equation and in
classic analysis, the next steps are to use the binomial theorem to expand that
which is based extracting the coefficients.
and then with some a little bit of algebra, we can get down to the result
that G of N equals 1 over 4 minus 2, 2N choose N.
and then we can use classic analysis Stirling's approximation with again,
quite a few calculations to finally get down to the result that the number of
trees is asymptotic to 4 to the N minus 1 over square root of pi N.
And again, these types of calculations are what we covered in analytic
combinatorics part 1, if you're not familiar with them.
If you are familiar with them, you know that there's a fair amount of calculation
involved here. and again, what we're going to learn to
do in the second part of this course is to use complex analysis in this case
singularity analysis to immediately extract the asymptotic result.
so that's what we're going to talk about later.
for this lecture we're going to look at lot's of examples where we just stop at
the generating function equation. So that's our goal is to use the symbolic
method to derive generating function equations.
that's what we're going to be talking about for the next couple of lectures and
then we're going to how do we get the asymptotic results out?
now a very standard paradigm for the symbolic method that really helps to
explain, or helps you to understand its power, is this idea of just, we use
fundamental constructs to define things that are quite simple and intuitive.
It almost seems too simple even trees, that's an extremely simple construction
that I guess is down to the result that we want.
Sometimes, they're very trivial or elementary, but at least we can check
that and confirm our intuition that they indeed work.
We'll see plenty of examples of that but then we can compound the constructs and
immediately build up more complicated kinds of structures.
there's lots of possibilities. The set of combinatorial constructions
really is a, is a language that has unlimited possibilities.
and it turns out that even with a simple one we describe, we can get lots of
classic combinatorial objects that have been described that have been studied in
great detail. We can easily describe them with a
symbolic method and get equations that the generating functions satisfy.
what these constructs do is kind of expose the underlying structure in some
way and then reflect that information in the generating function equation.
but a lot of times we're just exploring one path to a known result for again the
natural combinatorial logics, a lot of them that we're going to look at today.
but the main point is that we can study variations that where we try other
possibilities we have restrictions on things, and so forth.
And this is what comes up and practical applications, and there's an unlimited
number of possibilities. But the structure that we learn from the
fundamental and compound constructs just follows right through.
and, and we get results that really we couldn't even consider approaching
otherwise. and that's a very standard paradigm that
we'll see in application after application for the symbolic method and
for analytic combinatorics. It's a calculus for the study of
quantitative properties of large combinatorial structures.
Calculus means that we have unlimited possibilities, once we understand the
basic operations. so just in the context of trees lets look
at a few variations, just a very few variations on a theme.
so we said a tree is a node in a sequence of trees another variation is to say well
each node can have either zero or two children that's called a binary tree.
and again immediately you can write down a construct that's a variant on the basic
construct. this says a binary tree's a node and a
sequence of 0 or 2 binary trees, and you can construct things like that.
and that immediately gives the generating function equation, T of z equals z times
1 plus T of z squared, or we can do a variation where we consider multiple node
types. for example, suppose we wanted to
distinguish the nodes that have 0 children from the nodes that have two
children in a binary tree. this is important in computer
applications where binary trees are used explicitly as data structures to support
fundamental search algorithms and operations.
so in that case we're working, start working with, different, atomic elements.
to build up a combinatorial class the internal node is the one that we consider
to be of size 1. So, its generating function is z,
external nodes we consider it to be of size 0, so their generating function is z
to the 0 or 1. then we use a construction with both
types of nodes so a binary tree is either an external node, node with zero
children, or a binary tree with an internal node and a binary tree, that's a
node with two children. That with those definitions for what the
atoms are, again from the basic transfer theorems immediately transfers to again
an OGF equation, T of z is 1 plus z, T of z squared.
or we could enumerate by external nodes and switch the sizes and then it that
case we get T of z equals z plus T of z squared.
and it turns out actually, that all of these generating functions are related
and related to the catalan numbers. and there's interesting things that we
can learn combinatorial, but combinatorial from this manipulation but
for the present the point is that however we want to specify it it's very easy to
get the generating function that enumerates all these different types of
trees. so there's many more variations that have
been studied, and many of these are talked about in the book.
and the trees are so fundamental, there's other ways to look at them.
so gambler's ruin paths or context-free languages, or triangulations, and all
sorts of other combinatorial structures or equivalent to tree structures.
so these basic kinds of operations are going to lead to generating function
equations that help us enumerate a very, very broad variety of combinatorial
structures. so these are just some examples order
tree, we just talked about or binary tree or there's a thing called the
unary-binary tree, where you allow nodes to have 0, 1, or 2 children.
or you could have ternary or four-way trees or whatever else you wanted.
there's a thing called, bracketings which is a famous problem of Schroeder.
where we allow, we disallow unary nodes. It's the opposite of unary-binary a node
has to have either zero or greater than two children.
and that's related to the number of ways you can parenthesize N variables.
and again each one of these equations immediately translates to a generating
function equation and they're all different.
And in fact, you can have arbitrary restrictions on what the how many
children a node can have. and for any set then you can get a
generating function equation that describes the trees that have those kinds
of restrictions. there's plenty, there's applications for
all of these sorts of things and for not many more.
so that's an illustration of the idea that we can start with a fundamental
construct and get to variations that help us study a broad variety of things that
are structurally similar. Another example of that is strength,
again we start with a very basic fundamental construct, say the class of
all binary strengths. Well a binary string is either empty or
its a 0 or 1 bit followed by a binary string that immediately gives an OGF
equation B of z equals 1 plus 2 of z, B of z and that now immediately leads to
the the solution B of z equals 1 over 1 minus 2z of the number of binary strings
is 2 to the N. But then we can have all kinds of
variations on that theme. So one is say the the class of binary
strings that don't have a sequence of P or more zeroes.
well that string with no sequence of P or more zeroes is a string of zeros of
length less than P and followed by it's either that, or it's that followed by a 1
followed by another string with no zero to the P, just generalizing that same
argument. And that immediately gives a OGF equation
that the generating function for these strings, must satisfy.
And then we can find z to be in an equation, we know the number of such
strings. And there's lots of applications where
people want to know things of this sort. and this extends to being able to
disallow any pattern whatsoever. it extends to describing the numerator
strings in regular languages or in unambiguous context free grammars and
many many other implication. And again start with the basic binary
string. there, actually there's two ways to write
down a construction for a binary string. You could also say it's just a sequence
of 0 and 1 bits. Either way, you get to the same
generating function and or you could say [UNKNOWN], so M different letters or the
example I did exclude strings of zeroes or exclude a particular pattern we talked
about that in detail in part 1, lecture A.
and again, regular images and context free images.
Again, starting with the most elementary construction.
But then using the operations in natural ways we can study a broad galaxy of our
combinatorial structures. [COUGH] That's introduction to the use of
symbolic method for basic structures trees and strings.
[BLANK_AUDIO]
