So next, we're going to look at the, the full set of, basic operations that we're going to use to make labeled classes, and the symbolic method, which is the association from those constructions to generating function equations. And again, it very much parallels what we did for unlabeled classes in this other setting. So, we're going to use a disjoint union operation, the labeled product operation that I just described. and then we can build up a class by taking a sequence of objects from another class, or a set or a cycle of objects. In those correspond to the permutations earns and cycles of basic objects that I talked about as basic examples. and so, the semantics is very natural. the disjoint union is just copies of objects, a pair that's copy of objects from A and B. Labeled product is take one from A, one from B, relabel them in all consistent ways. Sequence is a sequence of objects, set is a set, and cycle is a cyclic sequence. and those are very natural and easy to see when we do examples. more important, we have the symbolic method which, if the, we have the exponential generating functions, A of z and B of z, for the combinatorial classes that we're using as part of the construction. Then the construction immediately gives us an equation for the exponential generating function. Same as for unlabeled if you take the disjoint union and have disjoint copies of objects from A and B, then the EGF is sum. And we'll look at the proof of this which is quite natural. For star product, it's the product. And again, that's by design. in the proof which we'll look at is quite natural, even in the labelled setting. for sequence if you have a sequence of length k it's just A of z to the k just by extension of the product. if you have a sequence of any length, then it's 1 over 1 minus and again we'll look at the proof of this. for set, it's A of z to the k over k factorial or for a set of any size it's e to the A of z. and for cycle, if it's a k cycle, it saves you to the k over k and cycle of any length that's log of 1 over 1 of a minus z. These are very natural and we will show the proofs in a minute. Just as an exercise it's wise to look at this star product transfer theorem for, for the small example that I showed before. whereas 1, 2 times 1, 2, 3 is equal to those ten objects. How does that work in terms of the exponential generating functions? Well, the exponential generating function for 1, 2 is just z squared over 2 factorials. Just one object. And for 1, 3, 2, it's z cubed over 3 factorial. What's the exponential generating function for this combinatorial class on the left? Well, there's ten of them and they have five objects, so that's z to the 5th over 5 factorial. so, 10 times z to the 5th over 5 factorial. that's, five factorial's 120, so that's z to the fifth over 12. And that's B of z times C of z, exactly as the transfer theorem says. You have the EGF for uh,[COUGH] the two classes, and you star product them, the EGF for the result is the product of the two EGFs exponential generating functions. And so, that is just to check for this small example in it works in, in general. and again, the basic instructions that I talked about in the set up are just applying of this, these basic theorems. unearned if the set of objects, cycle is a sequence, sequence of objects, and permutation is a linear sequence of objects and those are our examples. And the transfer theorems immediately give us the generating functions without having to count. they EGF for earns, is e to the z. It's a set of objects, it's a single object, EGF is g, and the theorem says you take e to that power for sets. For cycles, it's log of 1 over 1 minus z, directly from the transfer theorem. We don't have to reason about counting them. and for premutations, it's 1 over 1 minus z, again directly from the transfer theorem. Then we can extract coefficients from those generating functions to get the counting sequences. And again, of course, this checks for the basic instructions but that's the same method that we're going to use for any kind of combinatorial class. the, specify the construction use the transfer theorem to get a generating function, and then, extract information about the coefficient from the generating function. so, here's the proof of the transfer theorems. and I'm not going to dwell on these. they're quite straightforward and they're very similar to what we did for unlabeled classes in the last lecture. for this joint union if you want to the EGF for A plus B. if there's item in A plus B, then as a term z to the size of that item, the size of that item factorial. That item had to come from either A or B, so we can separate the terms into As and Bs, and that's just A of z, B of z. for the star operation, it's it's more complicated. As we did in the small example we simply choose some set of labels for the object that we took from A. There's A plus B choose A possibilities for that. and then the terms are z to the the size of A plus B, A plus B factorial. And if we group the ones for A and one for B, the A plus B factorials cancel out, so that the ones from A and ones from B are independent, just as they were for the unlabeled classes, which gives the product. again, it's extremely straightforward if we reason just based on the pairs of objects. And that one is the key operation the others follow immediately just from the simple equations on the generating functions. So, for example A of z to the k. so that's the number of k sequences of size N, z to the N over N factorial. so from the, just extending the product operation that's the generating function for that, is for taking a sequence of k items from an object, is A of z to the kth power. so it's just the product operation k times. but that same end if you sequence of any length, then you're going to be a sequence of size 0 plus 1 plus 2, and so forth. and so that's just 1 over 1 minus A of z. so that all directly follows simply from the product operation. now for cycles, if you take all the k sequences of size N and add them up, then you're going to see each cycle k times. So, A to the z to the k over k is, the generating function for the number of k cycles of size N. so that's just an argument based on algebra from this generating function equation. k cycle of, of objects from class A is A z to the k over k. And again, a cycle of any length, you just add those all up, and that's the natural log of 1 over 1 minus A of z. And again, the same kind of argument, if you take all the sequences of size N, you're going to see each set, k set, k factorial times. So that means A to the z to the k over k factorial is the generating function for the k sets of size N. k sets of size N, sorry, the k sets from A is A to the z to the k over k facotiral is the generating function for that. And again, summing those for all possible k gives the e to the A to the z for a set of items from A. So those are simple proofs, actually, but we won't need to consider them again, because the transfer theorems are so easy and so direct. so and, and again this is a repeat from the last lecture. But it's even more true for, well similarly true for labeled objects. The simple constructs that I've shown are quite elementary and confirm our intuition. but we can use the constructions to build up compound constructs in many different ways. And as we'll see, they give us a classical combinatorial objects of all sorts and expose their underlying structure. And we can go even further with variations on the classical objects with different restrictions. And we can get quite complex combinatorial constructions that maybe we need in modeling some real world problem. but we treat in precisely the same way as the elementary ones and we get the result of a generating function equation that it would be very, might be very difficult or complicated to otherwise analyze. Of course, there's some way, because underlying it all are the simple combinatorial equations that I showed but this approach is going to suppress a great huge amount of the detail. So we'll see this , in look at this in some examples right away for permutations. so a permutation is set of cycles. and that a well known in combinatorics and it's a lot of detail of this. In part one, lecture five, if you want to go look at detail. So you can write a permutation as, this is a permutation of 16 elements. It's just an ordering of the 16 elements. If you think of it as a mapping, say I want to go from the entry 10 and 4th position, it means I go from 4 to 10. And I look at 10, and that goes to 6, and 6 goes to 15, 15 goes to 4, that's the cycle. and so, the elements, starting anywhere, you can create a cycle, and then give a correspondence between permutation and a set of cycles. So, that's a, a set of cycles representation of this permutation. that's a well-known combinatorial bijection. But from the point of view of analytic combinatorics we can see that the counts of these sets are equal. Or we can understand better say, the structure of the cycles and permutations using combinatorial construction. so have, here's just an alternate way to use combinatorial constructions to count permutations that's we were talking about. Permuation is a sequence of labeled atoms. It's generating functions 1 over 1 minus z by the transfer. And if you pick out coefficient of z, you get the number of permutations. But say we didn't know the bijection and we want to count sets of cycles. Well then, we could use the construction that p star, it's really the same as P is a set of cycles of combinatorics of of atoms. P is a set of cycles of atoms. Then the transfer theorem immediately says that the generating function for that class is cycles of atoms as log of 1 over 1 minus z, and sets of that is e to that power. Well, e to the log of 1 over 1 minus e is just 1 over 1 minus z. So that's a different way of getting to the generating function. But we'll see that we can modify this argument to tell us about the cycle structure of permutations in more detail. and any way, we get the same result. So let's see a variation of that, and a famous variation of that is called derangements. and there's many ways to look at it, and again, there's lots of amusing stories about this in the lecture in part one on permutations on analytic combinatorics. So if you have n students and they throw their hats in the air and each catch a random hat, what's the probability that nobody get their own hat back? Well, that's called a derangement. If we count the permutations that have no singleton cycles then that's, and divide that by the total number of permutations, we get that probability. So and enumerating derangements is a simple modification of the derivation I just did for permutations. How many permutations have no singleton cycles? Well, we construct them by taking a set of cycles that are bigger than size 1. derangements are permutations with no singleton cycles and that then is immediately reflected in that that construction. Cycles of size 1 bigger than 1 it's, is the generating function for that is z squared over 2 plus z squared over 3 plus z 4th over 4 plus so forth. It's a natural log of 1 over 1 minus z, but leaving off the first term, the z for size 1. Or it's, another way to look at it is it's e to the log of 1 over 1 minus z minus z, subtract off the singleton cycles. so the generating function for derangements is e to the minus z over 1 minus z. now we can extract coefficients from that, now in, with a little bit of analysis, show that it's asymptotic to 1 over e. we'll show how to do this in a uniform way later on in the course, but anyway, for this case, it's not hard to convince yourself that the coefficient is asymptotic to 1 over e. and that solves the problem that probability that nobody gets their own hat back is about 36% that's a classic problem in combinatorics. From the standpoint of this course what we want to take away from that is, the simple modification of a basic construction, gives us an easy answer to this practical problem and it generalizes. so, how many, how many permutations have no cycles of length less than or equal to M. so that just generalizes the previous argument to put bigger than M there, and just leave off the smaller cycles. and that's e to the log of 1 over 1 minus z, subtracting off all the terms up to N. or it's e, rather complicated generating function, and now, extracting coefficients from that, using classical methods might be a challenge. so that's for the second part of the class to see how we get asymptotic of coefficients of functions like that. But for this part taking the construction and getting an equation on the generating function is a very simple process. or another uh,[COUGH] flavor of permutations that people study are called involutions. How many permutations have no cycles of length bigger than two? They're only one cycles or two cycles well, it's a set of one cycles per two cycles and the generating function is e to the z squared over 2. As we'll see, these two things are completely different analytically. and require completely different techniques for understanding asymptotics of coefficients. but from the formal standpoint of the symbolic method they're quite natural. and so we can have generalized involutions where we go up to size m and so forth. so that's an example how a simple commonitorial.g construction with variations can lead us, not only to a study of commonitorial objects that more close that mirror situations we see in the real world. but also give us immediately, through the symbolic method generating function equation. so we start with set of cycles of, of atoms and then we look at the arrangements, which is just the modification of that construction or involution where they are only built from size 1 or 2. We can generalize it in both ways to look at all cycles bigger than a certain size or no cycle bigger than a certain size, or actually, we can have arbitrary cycle length, constraints, and still get a generating function equation. That's an example of the symbolic method used to derive generating function equations by simple modifications a standard paradigm. And an introduction to the symbolic method for labeled objects itself and we're going to look at many other examples. and there's plenty of other things that you can do with permutations. what about the ones with exactly N cycles? Well, that's a set of size M of cycles. And so, that's the generating function for that. And you can imagine many other types of modifications of this. so that's an introduction to the symbolic method for labelled classes.
