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.
