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.
Labelled trees
Loading...
Del curso dictado por Princeton University
Analytic Combinatorics
16 calificaciones
De la lección
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.
Conoce a los instructores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Now we're going to look at constructions of labeled classes that involve trees.
And if you took part one, you want to pay more attention here.
We didn't really cover this much in part one.
so definition of a, of a labelled tree is just that you take a tree within nodes
and there's various types of trees that we talked about in the last lecture.
And it's the tree whose node are labeled with the integers 1 through n.
It's as simple as that. So you might want to know how many
different labelled trees there are of size n, and there's all kinds of
variations that we're going to consider as we did with unlabeled trees.
Is the order of the subtrees significant? Is there a root?
is there restriction on the degree of each node, and, there's an application
called increasing, where we want the labels to increase along paths on the
tree. so some of these questions are very easy
to answer, others are classic problems in combinatorics.
but our point for this section is that all of them are easily answered with
analytic combinatorics. Or at least he answered in a uniform
matter within a[UNKNOWN] commentory. So, now, again this is just getting
through the terminology before we go to the specific of different trees.
So, when we talk about rooted ordered labelled trees, it just means that the
order of the sub-trees is significant. So, we consider these two trees to be
different. if we talk about unordered, then we
consider those two trees to be the same tree.
The order is not significant. but of course if the root is labeled
differently or something, then we consider those to be different trees.
Those are known as Cayley trees. And there's applications for each one of
these as well. if we take away the idea of a root then
say these two trees. Would be considered the same.
Because you can deform one to the other. The have the same labels on the, on the
middle node. but if they have different labels on the
middle node then we consider them to be different trees.
and then, we have the idea of increasing trees.
where again, the order's not significant, significant.
But the labels on the paths have to be increasing.
And these two would be different because that path's got 1, 2, 4 1, 2, 3.
And that one's got 1, 2, 4. So those are examples of the things, that
we're going to be looking at. We'll also look at increasing binary
trees where, ordered subtree is significant, and everybody's got zero or
two nodes high as children. so that's labeling the familiar tree
structures that we talked about last time.
So how many different labelled, rooted, ordered trees of size n.
so there's one of size one, there's two of size two and there's 12 of size three.
So that is, there's, take each of the possible trees and there's 12 six ways to
label em. you just take all the permutations.
In both cases it's essentially a string of three nodes, and in fact this
generalized immediately, so you can immediately see that the number of
labelled root order trees of size n is n factorial times the number of unlabeled
trees, because you can just take... the nodes in the tree in any canonical
order and just, label them in factorial different ways according to that order.
so that's, a, combinatorial proof of, of this.
but we can also get it from, analytic combinatorics, and it's worth while to do
that. so, again, we write down our class and
our generating function. And, what is a labelled rooted ordered
tree? well, it's a root in a sequence of trees,
and using the star operation. that's all.
So, then according to the symbolic method, the generating function is z over
1 minus l of z. that's the exponential generating
function for label trees. that's exactly the same as the ordinary
generating function for unlabeled trees, that gives us the catlyn numbers.
But then what that means is, if we extract coefficients.
Then we take n factorial times the coeffient of z of n and label z.
So that's n factorial time the catyln numbers.
And that's the same as what I just said. There's n factorial ways to label a tree
walk. and so just multiplying it out you get a
ratio of factorials and we can use Stirling's approximation or other methods
to get get an approximation for the counting sequenece.
but that's not our point. For now, our point is that the generating
function equation for the exponential generating function is easy to derive
from a simple combinatorial construction z times sequence of z.
Alright, let's look at cayley trees which are the same except they're unordered, so
we don't care about the order of the root.
So now, there's only three ways to label the tree of size three with a root and
two children. you label the root, and we don't care
about the order of the way the children are labeled.
And then if you work through the different tree shapes of size 4 well,
there's 24 different ways to label that one, but, there's only, 12 different ways
to, label this one. You can assign the root one of the four
possible labels and then you have three different ways to label the one below,
and so forth. And, what's interesting, if you add this
up, you're starting to see, powers and actually The number of labor labelled
rooted unordered trees of size N, turns out to be N to the N minus 1.
Now we will talk about this proof later on, because these are special cases of,
what's called mappings, which is a more, intricant commonetorial object, but we'll
do this proof later on. For now you can think of the structure
as. Showing something interesting that, we
get all these strange, arguments and not many different ways to label things, but
it all adds up to such a simple formula. but then we can look at increasing Cayley
trees, so how many different Cayley trees of size N have increasing labels on every
path? again, we don't care about the order.
in this case, there's only only 1, 2, 3. There's only one way to do that one and
1, 2, 3, 4, like that. Three different ways to do this so ones
gotta be at the root, always and then your children can be two and three but
one of them, depends which one gets the four, or your children could be two and
four, but those are the only possibilities.
You can't have children being three and four because then there's no place to put
the two, and so forth. So there's a six and actually the number
of increasing Cayley trees is n minus one factorially.
And again maybe not so easy to see where that comes from.
But with analytic[UNKNOWN] they'll be a uniform way to derive this.
and then increasing binary trees. How many different binary trees are there
with increasing labels on every path? and so these are all the possibilities
for a small number of trees. there's more binary trees because every
node has the order is significant, every node has 0 or 2 children.
and so any, anyway, these are the possibilities in there's actually n
factorial different binary trees of size n.
And again, this is an easy result that has all this structure behind it.
it suggests a bijection and actually there is a bijection between increasing
binary trees and permutations. that's quite easy.
So let's look at the analytic commonotorics of increasing trees, and in
order to do that, we're going to introduce another construction called the
boxed product construction. And this is just an example that the
operations that we use in the symbolic method They're not necessarily a closed
set. it's not difficult to add more operations
to respond to the needs of different applications.
So in this case, the increasing facet of the application means that we need some
combinatorial operation that takes that into account, and that's what boxed
product is. So we're going to use the notation A
equals B box star C, it means the same as star except that we're only going to
consider the subset where the smallest element goes into B, goes into the first
one. So, our little example of 1, 2 box star,
1, 2, 3. out of these ten possibilities, this is
only four of them that have the smallest element in in the, from the first
product. So, and again the transfer theorem which
I'll give a proof in a second. if you do the box product and you have
the generating functions for b and c the enter, the generating function equation
is a prime equals b prime c. and so here's the proof of that.
so just with commonatorics. so the number of elements in a, you can
pick You have to pick the smallest one, for b, and then, you can pick the other k
minus one from n minus one and any one of these n minus one just came out one ways.
And then there's however many elements there are in b.
If there's of em, then there's gotta be n minus k and c.
So that's an equation convolution that gives a number of elements in a.
divide both sides by n factorial and multiply it by z to the n minus 1 and sum
and do the convolution and rearrange terms.
then we can separate into two different sums.
and that's a prime of z on the left, and b prime z, c of z on the right.
so and it's not the proof that's important.
It's how simple the transfer is. So let's check it for a small example.
So, again, this is 1 2 box star, 1 2 1 2 3 is those four things.
A generating function for that is 4 z to the 5th over 5 factorial.
A generating function for B of z is z squared over 2 factorial, and C of z is z
3 over 3, like that. so a prime of z is multiplied by 5.
5 times 4 is either is either 4th over 3 factorial b prime of z is z and that
checks. a prime of z equals b prime of z, times c
of c. So, we have a operation and we have a
transfer theorem. so then we can use that to enumerate
increasing trees, like increasing Cayley trees or increasing binary trees.
So for, Cayley trees, it's, a Cayley tree is z-box-star, a set of Cayley trees.
That just means z box star means the 1 has to go as the label of the root, and
the rest of them are labeled increasing trees.
So, from the transfer theorem, we immediately get the generating function
equation, q prime of z equals e to the q of z.
The b, in this case, the first one, generating function z, its derivative is
1, so it goes away, and then sets all left.
Q parameter is equal to q of z. That's an equation that the exponential
generating function of labeled increasing Cayley trees has to satisfy.
and you can solve that differential equation log 1 over 1 minus z works.
so its derivative is 1 over 1 minus z, and e to that power is 1 over 1 minus z.
so that means that the counting sequence is n factorial times the coefficient of z
to the n in that. which is just n minus 1 factorial.
so, that these a simple proof of the number of Cayley trees is n minus 1
factorial, using analytic commonatorics. Similarly for binary trees it's z box
times b times b, and that transfer's to b prime of z equals b of z squared.
And we can solve that one and get 1 over 1 minus z for that, which is a proof that
the number of labeled increasing binary trees is just an n factorial.
Again, analytic combinatorics provides simple proof of these results without any
kind of, counting arguments. and not only that, but it can be extended
to handle situations where there's restrictions on the degree of the nodes
and and many other things. and by the way increasing binary trees of
bijection with permutations again, we don't always find bijections like this
but this one's an easy one If you take a increasing binary tree in then you just
flatten it, then you get a permutation. Or if you take a permutation, you take
the smallest element, make it the root, and then do the same thing for the left
and the right, you get an increasing binary tree.
so that's an easy proof, that increasing tree's n factorial.
Not so easy for Cayley trees. That's a classical problem in
combinatorics, actually. okay, so again we start with a base, a
basic set of combinatorial constructs and we can consider the analysis of all kinds
of tree structures. and these are just a few of many many,
examples of the study of labelled trees. It's a classical topic in, combinatorics
but analytic combinatorics, allows us to handle all of these things in uniform
manner. That's an introduction to the study of
labelled trees using, combinatorial contstructions, and symbollic method.
How to derive equations by generating functions.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
