Labelled trees

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

19 notes

Princeton University

Analytic Combinatorics

19 notes

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.

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

Symbolic Method for Labelled Classes 18:36

Words and Strings 12:21

Labelled trees 15:25

Rencontrer les enseignants

Robert Sedgewick
William 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.

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.

Télécharger dans l'App Store

Disponible sur Google Play