Now we're going to finish up our, our study of labeled combinatorial classes by talking about mappings. so a mapping is a very simple concept. A mapping is an inward of length n. so it's a function from the integers one through n onto itself. so, we just, list, all possibilities. and it's pretty clear that the number of mappings is going to be, N to the n, for every, position, we can assign anyone of n different numbers since N to the n. Now that's simple enough. But actually there's the underlying structure that's fascinating and related to and arrising in numerous applications. Mapping as a function, from the set of integers from 1 to n onto itself. And so here's an example of a long mapping, where I had the numbers 1 through 37 and then down below I have the numbers 1 through 37 and they can appear multiple times. That's a mapping. Each one just has to be some number between 1 and 37. Now what's interesting is there's you can use a directed graph structure, also, to describe mappings. And they, expose the commonatorics of what's going on maybe better than the tabular structure. So for example, 27 goes to 20. and then 20 goes to 9. and then 9 goes to 26 and 26 goes to 1 and 1 goes to 9. so this is a special case of the sets of cycles that we had for permutation. But it sets of more complicated structures that this directed graph illustrates. so you have, there's natural questions that arise. And that are actually important in, in applications. so like what's the probability that it's connected? or how many different components are there? how many nodes are on cycles and how many are on trees? and then there's parameters of mappings that we'll talk about next time is, like what's the average time it takes to get from a node to its cycle? What's the average size of the cycle? All of these questions are of practical interest and [COUGH] analytic combinatorics, again, handles them all in a uniform way. So let's just look at a numeration, how many mappings are there of length end. Again, if we go like we did for trees we can look at different ways for labeling the different structures that might come out. And again, now there's definitely plenty of comlications in the number of different structures there are. there's only one way to label that one just one, two, three. or another way to look at it is just list out all the 27 mappings, and then see what the structure looks like. So, one, one, two. So that means one points to itself. two points to one. And three points to two. But that's also the same as three, two, two. that's where two points to itself and three points to two and one points to three. So those are all the different ways to label that structure. And there's six of em, six of em, two of em. And again, this complicated labeling and this complicated set of structures adds up to this simple result, n to the n. My correspondence with n words but this internal structure is definitely of interest. So with analytic commonatorics we're going to be able to take that apart and understand properties of the structure which is important in applications. now in order to do this we're going to need a powerful tool known as Lagrange inversion. and it actually is useful for the study of of any tree structure, and it's a very deep theorem, it has many applications in mathematics. we're going to use it in a, in a, in a, a pretty straightforward way, but anyway it's necessary to state it. I'm going to leave out the proof, because it's best understood via more advanced techniques than what we're going to cover in this course. but anyway, here's a, here's a statement of the so-called Lagrange inversion theorem. So it's, it's, the idea is it's about the inverse of a function. so I have a function f of u equals z. then the, it's inverse is the function u equals g of z. So for example if f of u equals u over 1 minus u, then solve for u and that's g of z equals z over 1 minus z is it's inverse. So the lagrange inversion theorem says that it, it gives away to get the coefficience of g from the form of f. So it says that if you have a generating function that satisfies the equation z equals f of g of z. so that's the, inverse, definition. in these conditions that f is zero and f prime of zero is zero. And if f prime of zero is not zero then, then the coefficient g sub n is 1 over n, time the coefficient of u to the n minus 1 and u over f of u to the nth power. so and that's what it is. so in our simple example, where f of u equals u over 1 minus u. Then the theorem says that the anti-coefficient, the generating function for g of z. Is one over n, coefficient of u n minus one, in one minus u to the n, because u over u over one minus u is one minus u, one minus u to the n. Coefficient of u to the n minus one, that is minus one to the n times minus one to the n minus one, and divide by n we get minus one to the n minus one. And that's exactly what g of z is, g over 1 plus z. so you can study this and, and learn about inverses, but really we're going to be applying this theorem in pretty much a cook book fashion symbolically, just like this. so, from the point of view of analytic commonotorics, it's an analytic transfer theorem that gives us coefficients once we know a generating function, 'cuz in recursive structures like mappings and trees, we often encountered generating function equations like this. in fact, we use a, a more general formulation called the Burmann form of the Lagrange inversion theorem and that's if we forgot a, another function Uh,H of u, and you want the coefficient of H of g of z, then we put in H prime, and, and it's just generalizing the basic theorem from H of u equals u. so this is the form that we're really going to use for mapping. and again, it's, this is a, a deep and wonderful theorem that I don't have time to do anything more than Uh,[UNKNOWN] so that you can understand how we extract coefficients. so, just as a classic application for catalan numbers, so this is with ogs that we did last time. binary tree is a node or two binary trees. I'll just count by external nodes so we have that OGF equation. so rewriting that is z equals t of z minus t of z squared. So that z on the left hand side, that makes this, a candidate for a Lagrange inversion, so, the theorem says if we want the coefficient of z to the n in t of z, we're just going to take, f of u be u minus u squared. So then we got z equals f of z, f of g of z. so, u minus u squared, t of z minus t of z squared. so we took f of u equals u minus u squared. So we want u over f of u. So that's u over u minus u squared. That's one over one minus u. So, we have co-efficient of u to the n minus one and one over one minus u to the n. and, just, use, the standard generating function for one over one minus z to the n we get the Catalina numbers out. So that's a classic application of a Lagrange inversion. and we can use it for other types of tree structures, we get other types of f of u in the same method, is going to work, and we'll look at it from a general point of view later on. but now let's look at Cayley trees in mappings. So, so Cayley trees are labelled rooted unordered trees. so they're special case of mappings where every node points to just one node. And there's one root, and it's connected. so, the construction is simple. a Cayley tree, is a tree, connected to a set of trees. the transfer theorem then gives us, immediately, C of z equals z e to the C of z. That's the exponential generating function for Cayley trees, labeled root of unordered trees. And so that means that z equals c of z over e to the c of z. So that means we can apply Lagrange inversion with f of u equals u over e to the u. c of z over e to the c of v. And so, that's Lagrange inversion. U over e to the u. U over u over e to the u is e to the u, so the number, coefficient of z to the n is 1 over n, coefficient u to the n minus 1 in that. that's coefficient u to the n minus 1 and e to the un, and well, e to the un, that's some of k factorial, you went to the k over k factorial, coefficient n minus 1, in that is n to the n minus 1. So, the, number of Cayley trees with n nodes is n to the n minus 1. So that's a direct proof with analytic combinatorics. Now it does depend on Lagrange's inversion, but Lagrange's inversion is a very general tool that we can use in this same way for many similar problems. So that's, Cayley trees. now it suggests a some kind of bijection between Cayley trees and words with n minus or say with, in mappings with a constraint on it, but that's actually one of the classic problems in commonatorics is to find a simple bijection. Okay, so now what about mappings? Well let's move one step up. so a mapping is got cycles of Cayley trees. So that is you have a Cayley tree and, and then maybe the root note is on a cycle or maybe it's a single cycle of itself. so that's, connected components in mapping. So, or this is how many cycles of Cayley trees are there. And so these are just one connected component. Those are the mappings that have just one connected component, so there's 1 of size 1, 3 of of size 2, and 17 of size 3. so that's, labeled cycles of trees and those are all the ways to label that and, and so forth. so the answer to that is more complicated. and so let's look at it from the standpoint of analytic commonotorics. So here's a cycle of Cayley trees. You take a cycle and then take a Cayley tree going into any element on the cycle. So that's just an example, it's a special case of a mapping. but the construction is simple. A component is a cycle of Cayley trees, and then the transfer to generating functions is simple. the exponential generating function for cycles of Cayley trees is log of 1 over 1 minus C of z, where C of z is the exponential generating function for Cayley trees. Now, what about extracting coefficients? Well here's where the Berman form of Lagrange inversion comes in. We still get to use u over e to the u, but now we have this other function h of u which in this case is log of 1 over 1 minus. So, coefficient of z to the n, in log of 1 over 1 minus c of z, where c of z equals u over e to the u, you just plug into the formula and take the der-, so h of u is log over 1 over 1 minus u. We're supposed to use h prime, so that's 1 over 1 minus u and then the u over f of u to the n is e to the u n, just as before. So to find the number of cycles of Cayley trees, its coefficient is z to the n and, and y of z is one oven n coefficient u to the n minus one in that function. and that one is a convolution because you've gone one over one minus u times u to the un, so it works out to that convolution, and then this is just changing n to n minus k, and then the thing that we want is N factorial times coefficient z to the n and y of z. that comes out to this expression here. Hm, and this is a well-known function known as the Ramanujan q function and you can look in part one of the course to where we talk about the asymptotics of that function and we'll also talk about asymptotics of this again. when we get to complex asymptotics in the second part of, of this course. so this, this problem doesn't have so, so simple an answer, in, but, it indicates, the structure that lies, underneath this. and then what we really want to finish the job is the number of mappings, how many different mappings are there? A mapping is a set of cycles of Cayley trees, couldn't be simpler. and then the equation is A cycle of Caylee trees is log one over one minus a set of those is e to that power, so we just get one over one minus c of z. Again that's ripe for use of a Berman form where now we use the h function as 1 over 1 minus u, and then f of u equals u over u as before. So now the dif, derivative of h is 1 over 1 minus u squared so it's the same as on the previous slide except we have a 1 over 1 minus u squared times u to the n. and then if we do the convolution that time on this one then we get seems like a slightly different form of it. but actually this one kind of telescopes and gets to the answer n to the n over n factorial. so the end result is the number of sets of cycles of Cali trees is just n to the n. Now quite surprising that we get down to that simple result. But we have a clear explanation, explanation of all this structure through the analytic combinatorial. And that's extremely important when we come to analyzing parameters of these structures, that would be the subject of the next lecture. So, that's an introduction to, mappings, using analytic combinatorics.
