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.
Basics
Loading...
En provenance du cours de Princeton University
Analytic Combinatorics
16 notes
À partir de la leçon
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.
Rencontrer les enseignants
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Today we're going to talk about labelled combinatorial structures which we use
exponential generating functions to analyze.
Again, we're going to have a set of combinatorial constructions that we can
use, both to specify the structures and to immediately transfer to equations on
generated functions. this is the in the overview, this is the
second lecture on analytic combinatorics from the symbolic method.
and again, we're going to follow the same general approach that we did for
unlabeled structures and ordinary generating functions, where we have a
specification that's automatically turned into a generation function equation and
then later in the second half of the course we'll talk about turning those
generating function equations into the asymptotic estimates that we're looking
for. Now I want to give the same warning I
gave at the beginning of the last lecture.
quite a bit of this lecture is a quick review of material that we.
Went through in much more detail in Part one of the Analytic Combinatorics Course.
So one consequence of that is this lecture's a little bit longer than usual.
If you took Analytic Combinatorics Part one, and are bored because you understand
everything, that's great. Just fast forward through.
there's some new material on labeled trees and then do the exercises, or use
this as an opportunity to review the material.
if you're starting with this course, and you find that things are moving too fast
you can always go and see some details and motivating applications, in the
earlier course. okay, so let's talk about the basics of
labelled structures. so the idea is that, objects in labelled
combinatorial classes are composed of atoms and if there's N atoms, they're
labelled the integers one through N. So for unlabelled objects there had to be
a difference in structure for the objects to be different.
for labelled objects we add the extra constrains that it's the way that their
label makes for different objects. So these are two different labeled
objects because the labels go in different order around the square.
You can't transform one into the other. Where these are different labeled objects
because the one without degree three has got a different label in each of the
cases. So there's many more possibilities for
labeled objects. and as we'll see, that's why we use
exponential generating functions instead of ordinary generating functions.
So here's an example. Cycles of labeled atoms.
How many cycles of labeled atoms are there?
Well, you, you make a cycle, so here's a cycle of four labeled atoms, and you fix
one item, say say the four, then You have all permutations of the remaining n minus
one items make a different labeled object.
So, it's easy to see that the number of different cycles of labelled atoms is n
minus 1 factorial. so, but then we can look at a more
complicated example. How many unordered pairs of labelled
cycles of size n are there? so there's three different unordered
pairs of label cycles of size N. you got one, so it's a pair, so one of
them has one object and the other one has two.
there's Now you can pick one of the three labels for the one that has one object.
And then, there's only one way to label the one that has two objects.
So there's a total of three different, unordered pairs of labeled cycles of size
n. for four, there's 11 different, you can
pick, you can have one in three, you can label the one object any one of, the four
ways. but then the cycle that has three objects
can be in either orientation. They can be two, three, four or two,
four, three, on the top example. so that makes, eight, or you can have 2 a
pair of cycles of size 2 each, and then there's three different ways to label
them essentially by choosing out of the four the three different possibilities.
And remember it's an unordered pair. So 1, 2 in the left and 3,4 in a right
its the same object as 3,4 in left when 2 in right .
So that's eleven for four and how many for five and the answer is that it turns
out to be the sterling numbers of the second kind and we will talk about that
probably in the next lecture. Okay, so here's the basic definitions
that we're going to work with, and these correspond precisely to the basic
definitions that we used for unlabelled classes.
The first, we say a set of n items is said to be labelled if they can be
distinguished from one another And without any loss of generality we use the
labels 1 to n to refer to the to the atoms.
So a labelled combintorial class is a set of objects build from labelled atoms and
also is an associated size function. Again, just as before with unlabelled
classes. So we use exponential generating
functions and we associate with combinatorial labelled classes, and
that's just a formal power series. Reads a variable z, the function a of z.
It's the sum over all objects that belong to the class, z to the size of the
object, divided by the size of the object's factorial.
That's what makes it an exponential generating function.
so, and just as With unlabeled classes. We have the fundamental identity that's
elementary, that you can express the generating function as the sum from N
bigger than 0, A N, the number of objects of size N, z to the N over N factorial.
And that's elementary because we just collect terms all the objects of size N
there's a sub n terms of size n and that's then an identity for the
generating function. And that means that, if we know the
generating function, a of z, and we want to know the number of objects of
size n, we just find the coefficient of z to the n, in a of z, and multiply by n
factorial. so that'll be our goal later on.
For right now, we're going to talk about how to build combinatorial classes and
how those constructions lead us to, equations that the generating function
must satisfy. With the symbolic method, just as for
unlabelled classes, we specify the class and at the same time characterize the
exponential generating function. So let's look at some basic labeled
classes. So one is called an urn.
That's just a set of labeled atoms order doesn't matter.
There's actually only one[COUGH] urn of each size, because the label doesn't
matter. It's just a set of atoms.
So that means the counting sequence, the number of urns of size n, is just one.
And what's the exponential generating function?
It's just sum of z to the n over n factorial times one, that's just e to the
z. That's a basic labelled class, the urns
the exponential generating function is e to the z.
permutations, that's another familiar labelled class.
A permutation is a sequence of labeled atoms.
And that's, here's the familiar, there's 24 permutations, of size four.
So, the counting sequence, the number of permutations of size n, is just n
factorial. What's the exponential generating
function. It's just one over one minus z.
The sum, n bigger than zero, n factorial Is the counting sequence times z to the n
over n factorial, 'cuz it's exponential generating function.
That's just the sum of z to the n, and that's one over one minus z.
That's a second basic example of a labelled class.
And a third one is a one that I introduced at the beginning.
It's a cycle. A cycle is a cyclic sequence of labelled
atoms. There's n minus one factorial cycles of
size n. So what's the exponential generating
function? It's n minus 1 factorial, z to the n over
n factorial. That's sum of z to the n over n or log of
1 over 1 minus z. So those are three basic label classes.
And they actually serve as the foundation of the commonotorial constructions that
we're going to consider. Now, the operations that we perform on on
label classes in order to create combinatorial constructions are based on
this operation the product operation. we had a product operation from unlabeled
classes, which was the Cartesian product, where we take one item from each class to
make a pair. Now this operation, called the star
product operation for labeled classes is the analogue to the cartesian product.
So, given two labled combinatory classes A and B, their star product, or labled
product is the set of ordered pairs of copies of objects, one from A, one from B
But they need to be relabeled in all consistent ways, and here's a very small
example. If we have a class that consists of a
single two cycle and another class that consists of a single three cycle and we
take the star product, we get a class that consists of ten pairs of objects.
We have the two cycle and the three cycle but we need to relabel them in all
consistent ways. We want to use the labels one through
five and we have to make sure in the three cycle that we maintain the
orientation. One to two to three.
Smallest to middle to largest. So for example on the left he shows all
the ways to assign one to the two-cycle. It can be with two, three or four and
then what's left over gets assigned to the three-cycle but in the order;
smallest, middle, largest, as we go clockwise around the cycle.
And then next is the two cycles with 2, without 1, there's 3 of those, with 3, 4,
and 5. And again, the ones that left over, the
labels that get left over, get assigned to the three cycle in the order smallest,
middle, largest as we go around clockwise.
And then there's three, four and three, five and again just two possibilities and
then finally four, five with one, two, three.
So that's the star product example of the star product for simple, labelled
classes. As you can see, the possibility
multiplies but this as, as, as you'll see is a perfect analog to Cartesian product
that let's us build up labelled combinatorial classes of remarkable
richness and complexity. for example, again you use a familiar
example. You can create permeation just by taking
Star products of Atom. So a single, permeation of size 1 is only
1, its just a Atom labeled 1. If you take the star product of 2 Atoms,
all you can do is label the first one 1, in which case the second one has to be
labeled 2. Or we can label the first one 2, in which
case the second has to be labeled 1. That's Z star Z, that's the permutations
of two elements. For each one of those, if you take the
star product again with another Z. then there's three possibilities, that
essentially labeling the first item either one two or three and then,
labeling the next two items, uh,[COUGH] has to be a sequence.
So, I, in all consistent ways just put the next two, the labels that are left
order, over, in the order. so that's the first three, and then the
second three is what you get in the star product of one and two one.
It's again, first one can be labeled one, two, three, and the others are labeled in
reverse order. And then for example the second
permutation in that list, two, one three, if we star product that with another z
then we get one, two, three, four, and then the remaining labels go in the
order, middle, smallest, largest. And then we get four possibilities.
For each one we get four possibilities. So that's a way to specify the set of
permutations using the star product operation.
and just as with the unlabeled classes we can write a squared for a star a, a cubed
for a star a star a, and so forth. and that's the simple example of a
combinatorial construction. We say that the permutations of length n
are z to the nth And we're going to next look at many other examples of
combinatorial constructions. But that's the basic operations for
constructing labeled classes.
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.
