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.
