Next we're going to talk about another important class of combinatorial classes that has to do with labelled objects. And I'll explain the distinction between labelled and the unlabeled ones that we talked about and then look at some interesting problems. So labelled combinatorial classes, the objects have N atoms, but we consider the atoms to be all different. And to just make that clear, we label them, consider them to always be labelled with the integers one through N. So for just [COUGH] schematically for unlabeled objects, you can consider those two objects to be different. They have a different structure. But when they're labelled, [COUGH] there's different ways to label them that make different objects. For example, that's two different ways to label that square. [COUGH] So in the one on the left, 1 is connected to 2 and 4, the one on the right, 1 is connected to 3 and 4, they're different. And this one, it's not always clear how many different ways there are to label things. In the one on the right then there's three different ways to label that, either 1, 2, or 3, there's actually four ways. 1, 2, 3, or 4 are going to be the ones that are connected to everybody else. So there's a big difference in studying the number of different objects because the labels provide so many more possibilities. In fact, when we're working with labeled objects, we use exponential generating functions for that reason. And that'll become clear as we move along. So let's look at some basic simple examples again of labelled objects. So that's what we call an urn. And so an urn is a set of labelled atoms. So in a set, the order doesn't make any difference. So, again, there's only one of each kind. We could use this definition of unary numbers. And later on, you'll see why we use this characterization and it'll be very clear. So there's only one of each kind, but now we're going to use exponential generating functions. So the exponential generating function for urns is E to the z. That's one of each kind, z to the N / N factorial summed is e to the z. So that's our first basic example. The next one is a familiar one, it's permutations. A permutation is a sequence of labelled atoms. Sequence means the order is significant. Atoms are labelled so every possible ordering of the atoms is going to give a different object. So there's 2 different objects of size 2, either 1, 2 or 2, 1, 6 different objects of size 3, 24 different objects of size 4, and so forth. So what's the exponential generating function for permutations? Well, there's N factorial permutations of size N. And so the exponential generating function is that divided by N factorial times z to the N, which just leaves us with sum of z to the N or 1 / 1- z. So that's another basic combinatorial class. [COUGH] The N factorial serves to stop the generating function from blowing up too much because of all the different possibilities induced by the ordering. Here's another one, a cycle. A cycle is the cyclic sequence of labelled atoms. So everything is connected in a circle, but now there's fewer of each type. And in fact, actually, if you study it for a minute, if you just fix on the largest to the smallest element, then you can see that the others are permutation. So actually the counting sequence is (N- 1) factorial. So what's the exponential generating function for cycles? Well, it's the sum of (N- 1) factorial z to the N / N factorial, which everything cancels but an N, so it's natural log of 1 / 1- z. So that's another basic combinatorial class. Now it's very characteristic of analytic combinatorics to start with extremely simple derivations in classes like this, but then combine them in interesting ways to provide answers to analytic problems of interest. So what about the analog to the Cartesian product operation? Well, it's much more complicated for labelled classes. When we take the product of two classes, so we're going to say, this first example 1, we call it the star product. 1 star product of 1, 2, 3, what we're going to get is object of size 4, but they have to be numbered from 1 to 4. And what the combinatorics requires is that we do that numbering 1 to 4 but we do it in all consistent ways. So in this case, the second argument is a sequence that's in increasing order. So when we renumber, we have to put that in increasing order on each one of the possibilities. So we can assign 1, 2, 3, and 4 to the first one, and then the reaming labels, we assign to the remaining 3 atoms, but they have to be in increasing order. And here's a more complicated example, where we take the star product of a two-cycle and a three-cycle. Again, when we do that, we get 5. We have objects consist of five atoms that have this structure, a set of a two-cycle and a three-cycle. The atoms have to all be numbered with 1 through 5, and we have to do it in all possible ways. So in this case, you can choose any label. So there's only way to label the two-cycle. And then you can choose 5, choose 2, or 10 different ways to label the two- cycle. So, the first column is, with the top one being 1, you can have 2, 3, 4, 5 for the bottom one. Second column's top one being 2, 3 and 4. Then, after you've labelled the two-cycle then you take the remaining labels and assign them to the three-cycle, but you have to be consistent and maintain the order. So, for example, with 3, 4, in this case with 3, 4's, the labelled two-cycle, the remaining labels are 1, 2, and 5, and they have to go in that order. So that's the star product operation relabeled in all consistent ways. And when we get to applications, we'll see why that's not just intuitive, that's fundamental to working with labelled objects. So with labelled objects, since you can tell the difference in the ordering, we have more basic constructions and it's a much richer set of operations that we're going to work with. And actually, the ones that I'm giving work for labelled and unlabeled are only the beginning. Research is ongoing and people have developed many, many more constructions than I'm going to present here. So [COUGH] plus is the same, you take copies of objects from A and B, but you relabel in all consistent ways. Star product is where you take ordered pairs of copies. Sequence is similar to what we did for a unlabeled. It's A plus A star A plus A star star A, and so on and so forth. But you could have sets of objects, like we did for urns. And you can have objects arranged in a cyclic sequence for example. So those are the constructions we can use. A richer set of constructions leads to a richer set of objects we can talk about. Again, what's important is that we have a transfer theorem. If we have combinatorial classes, and we know their EGFs. Then whatever operations we pick from that list. We're going to know the EGF of the result of that operation. As before, if we do disjoint union we have the sum. If we do the labeled star product. We have the product of the generating functions. If we do a sequence of k objects, it's like A of Z to the k. A sequence of any number of objects. It's summing those it's 1 over 1 minus. If we have a set, it's A to the z to the k over k factorial. So that's a set of size k, and a set of any size is the sum of those is e to the A of z cycle is a z k over k, and cycles of any length. Cycles of size k is that any length is log of one over one minus a z. So if we know the generating function for combinatorial class. When we perform one of these operations we know the generating function for the result, and that's extremely powerful transfer theorem. It's the basis for the symbolic method. So let's just look at the basic constructions of the basic objects using these operations. So urns, urn is a set of atoms. And that immediately translates to e to the z form the transfer theorem for sets. And as we saw, that gives the counting sequence Un equals 1. Cycles, a cycle is a cycle of atoms. And again, immediately from the transfer theorem, that tells us that the generating function is log of 1 over 1- Z. And therefore the counting sequence is N factorial times coefficient C to the N in that, which is N- 1 factorial. Permutations, as with bit strings there's two different ways to define permutations. You can say a permutation is a sequence of items and then read immediately from the transfer theorem that the generating function for permutations has to be 1 over 1- c. Or you can say, a permutation is either empty or the star product of an atom and a permutation. And that will generate all possible permutations. That immediately translates to P(z) = 1 + zP(z) and then solving for P(z) gives the same result. And then the counting sequence is N factorial times the coefficient of z to the N in that, which is just N factorial. So those are just the starting point for some basic constructions. The proofs of the transfer theorems, again they come just immediately from the definitions and from generating function counting the way that we talked about earlier. So A plus again is separate into B disjoint sets, and that immediately gives the result. First star, it's a conclusion of the type that we've seen before, but let's take a look. So, to do all different re-labelings. So, we take one alpha from A and beta from B, and to do all different re-labelings. It's alpha plus beta, choose alpha. Just like with the example I did with the cycles. And then. So that's a number of ways you can relabel. And then the size of an object composed of an alpha and a beta is e to the alpha + beta. And again, the factorials are from alpha + beta factorial. And then if you take that complicated sum, the alpha plus beta factorials cancel, and you can separate out CV alpha or alpha factorials. Either beta over beta factorial to get that it's a product. Again, that's a complicated convolution, but this is the only time we have to do it. And for the other operations, I have a slide that's got lots of dense math on it, but it's pretty simple. So as we saw before, A of z to the k is the number of k sequences. It's the exponential generating function for the number of k sequences of size N. So that's just as we saw several times before and if you add those all up for a sequence of any length, you get 1 over 1 minus z. But if you have all the K sequences of size n. Then you're going to have each k cycle of size n appear k times there in each cyclic orientation. So that means that A of z over, to the k over k is the EGF for k cycles, for cycles of k objects and then summing all those up gives the result for cycles of any length. Similarly of you have all k sequences of size N you're going to have all sets appear k factorial times. So that means that A to the Z to the k over k factorial is the exponential generating function for the number of k sets of size N. Summing all those up give the result that for any set. It's e to the A(z). So these are worthy of study. But they're very straightforward and immediate from the definitions. And the basic ideas of generating function counting. So let's look at a much more interesting example. So, the idea is that we have these operations. We can combine them in various interesting ways. And actually, as we'll see in part two. There's, every way of combining these basic operations leads to a combinatorial class that people are studying in detail. But there's many more operations we can throw in as well. So let's look at this, this is a famous one. How many different sets of cycles are there of labeled atoms? For example, for three atoms you could have a cycle of size three. There's two different ways to label that, or you could have one cycle of size one and another cycle of size two. And there's three possibilities for labeling that, or you could have three cycles of size one. So it's a total of six sets of cycles of labeled atoms. And if you work it out for four on the right is all the possibilities of sets of cycles of four atoms. You could have what'd be four singleton cycles, or you can have one cycle of size four. And there's six different ways to label that one, or you can have something in between. All the possibilities are laid out here. You might recognize the numbers. And yes, there's N factorial sets of cycles of N labeled atoms. And what we'll look at next is how we learn that from analytic combinatorics. And it's not just instructive. It forms the basis for us to solve problems that we couldn't otherwise solve, as you'll see. So let's use our regular methodology. We have to articulate what our class is. So it's P*, is the class of all sets of cycles of atoms. Number of atoms is the size. The EGF, as usual, brings together its coefficient is z over N factorial, is the number of sets of cycles of atoms. The atoms are just labeled atoms, for labeled classes it's always the same. [COUGH] What's our construction? A, nothing more than saying a set of cycles of atoms is a set of cycles of atoms. That's what the math says. And it immediately translates from the transfer theorems to cycle of z translates to natural log of 1/1-z. Set of something is e to that power and that's just 1/1-z. Therefore, the counting sequence of n factorial is n factorial. That's the same as for permutations and again, that's a very quick result, it just comes from the combinatorial description. A set of cycles that we could get the generating function for sets of cycles immediately from the transfer theorem. Now this is a well known combinatorial bijection, a permutation is a set of cycles. And to see that, you'd start anywhere. Say we'll start at 4. So here we have the permutation, and then we have the index of the sequence, where is it in the sequence. So, if we start at the fourth thing in the sequence, or the fourth enter in the permutation, it says 10. So we go to 10. And 10 says the tenth entry in the sequence is 6. So we go to 6. And sixth entry in sequence is 15 so we go to 15. And the point is as you see from this example eventually you're going to get back to where you started. That's a cycle. We can depict that thing just like this, just when you go from 4 to 10 to 6 to 15 back to 4. And if you've already done an item, ignore it, otherwise do this process, you can convert any permutation into a set of cycles. And it's a worthwhile exercise to figure out how to reconstruct the permutation from a set of cycles, but that's a well known bijection. So that brings us to our first actual problem that you might not know the answer to. Or you might because it's a classical problem. But we'll get to one that you don't know the answer to. And that's the derangements problem. And this is a famous problem from the 18th century. Usually, well at that time it was cast in this way. So you have n people who go to the opera and they leave their hats on a shelf in the cloak room but they all look the same. And so, when they leave they each grab a hat at random, and the question is, what's the probability that nobody gets their own hat? So, In terms of combinatorics, we refer to this as a derangement. Nobody gets their own hat, that means there's no singleton cycle. That means that that getting your own hat means that if you're in position four, it's the fourth item. And that's a singleton cycle. So the question is, what's the probability that the permutation is a derangement, or how many derangements are there. Now, just as an amusing aside, this problem has been posed in the centuries since in many different ways. That’s the classical opera way. So some people say well a professor returns exams to students by passing them out at random, what's the probability that nobody gets their own exam. So a lot of people use that where you're posing the problem in combinatorics classes. Or a more fun way to do it is the drunken sailors. So you have a group of sailors that are a bit inebriated and when they get back home, they wind up sleeping in a random cabin. So what is the probability that nobody winds up in their own cabin? Or maybe more relevant to college students is, got n students who live in a single room and they get also in a state of inebriation. What's the probability that nobody ends up in their own room? That's all the same problem. And to solve that problem, what we want to do it count derangements. So derangements are permutations with no singleton cycles. So this is our table of sets of cycles, which are equivalent to permutations with the ones that have singleton cycles grayed out. So there's nine permutations of size four that have no singleton cycles. Probability that nobody winds up with their own hats is is only 4 of 9 over 24. And so, this maybe is not a familiar sequence. So let's see how to analyze that with the symbolic method. Now we'll just go through our [COUGH] regular regiment. We’re going to find D to be the class of all derangements. Size is number of atoms. Standard labeled atoms. Generating function is always the same. Exponential generating function and so what's the combinatorial construction? So, one way to phrase it is this way. A derangement is a set of cycles where the length of the cycle is greater than 1, and we just indicate that with cycle greater than 1 of atoms. Permutations is a set of cycles of atoms. This one excludes the ones of length 1. That one immediately transfers. But derangements are permutations with no singleton cycles is what it says and so set is E to the whatever it is and what's the generating function for the cycles of length greater than one? Well the generating function for all cycles is Z plus Z squared over 2 plus [INAUDIBLE] like that and we're just leaving out the first term. So that immediate translation and that's the same as log of 1 over 1 minus Z minus Z. Is that infinite series is exactly log of 1 over 1 minus c minus c, and if we simplify that we get e to the -z /1 -z. Media translation to the generating function, another way to derive it which is maybe even easier to understand is we can say that what is a permutation. A permutation is the set of singleton cycles that crossed with a derangement. And so that's another way to phrase it. And that one immediately translates to e to the z d of z equals one over one minus z and solve for d of z and get the same result. So symbolic method gives us the generating function. Now extracting coefficients from this one's a little more complicated. We actually did it already in our lecture on asymptotics. So that's the result is that it's asymptotic to one over e and let's just look at each of the elements of that. So first of all, we're lookin and since we want a probability, it's convenient that we're using exponential generating functions. And our probability denominator is N factorial, so we're taking advantage of that [COUGH] coincidence. It's not really a coincidence, but in this case it works out. So to get the probability we just look at the coefficient of z to the N in the generating function. Not N factorial times z to the N because it's going to divide right now. So [COUGH] that's a D to the N over N factorial and what's that coefficient? Well, it's a convolution e to the minus z times one minus z. You just do the convolution, the coefficient of Z to the N and that is the sum of k from zero to n and minus one to the k over k factorial. And that's a straight convolution. Then that's a sum that we looked at as one of our examples for bounding the tail in the asymptotics lecture. To show that's asymptotic to one over e and that's very close to one over e. We're going to look at an easier way to get this at the end of this lecture. But the symbolic method gets us there and then provides practical solution to this kind of problem. The actual chance that if you go to a party and get yourself in a state of inebriation and line up in a random room. You've got a pretty good probability that nobody ends up in their own room, 36%. Or maybe a way to tell your parents about this problem is when students graduate and throw their hats in the air and everybody catches a random hat, 36% probability nobody gets their hat back. Actually, your parents probably want you to get your or the rental company probably wants you to get your own hat back. And so there's the idea of generalized derangements. So if you've had a random hat, you can always get your own hat back by following the cycle. So student four wound up with ten's hat. She can go to ten and ten's got six's hat. The she can go to six, six has 15's hat. The she'd go to 15 and 15 there's her hat. So following the cycle will get your hat back. So then now we have the more general problem, what's the probability that all cycles are of length bigger than m? That everybody's would have to follow at least M friends or M people and M random people can get their hat back. So that's the generalized derangement problem, what's the probability that all cycles are of length are bigger than M. Now that problem is much more difficult to analyze but with the symbolic method we can get right to the generating function. So it's just generalizing the argument that I just gave. D sub N is a class of all generalized derangements. No cycles in a linked list that are equal to N. Everything else is the same. So the construction is, it's a set of cycles that are bigger than M [INAUDIBLE]. That translates directly to generating functions, you just start at Z to the M + 1. So it's the same series now starting at Z to the M + 1. Or that's log of 1 over 1 minus z minus z squared over 2 all the way up to z to the M over M. And simplifying that, we have e to the minus z minus z squared over 2 minus z cubed over 3, so forth up to z big M over m over 1 minus z. So that's the generating function that we get immediately from the symbolic method. And quite simply without the symbolic method, you might have some trouble getting to this generating function on your own. So that's certainly a lot of these things is possible to do because what's behind the symbolic method is so simple. But the symbolic method really makes it so that a child can do it. So that's a generating function equation. Now to find the answer to this problem, we need to extract coefficients from this equation. Now that one, not so clear. That would be an M way convolution and go ahead and try to extract coefficients from that one. So that's going to motivate, how can we find the coefficient, how can we estimate the coefficient of z to the N in that complicated function? That's going to motivate the second part of analytic combinatorics, the analytic transfer theorems. But that's a basic introduction to symbolic method for labelled objects.