0:00

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.

Â 5:11

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.

Â 7:55

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.

Â