Okay, now we'll talk about mappings. Which is a combinatorial structure that is related to many of the things that we've studied. And it really is an appropriate topic on which to close. And it's kind of a poster child for analytic combinatorics. So what is a mapping? A mapping is an N-word of length N. So that is, we've got N characters and every one of the characters can be anything from 1 to N. So obviously, there's N to the N. Different N-words of length N are mappings. That seems simple enough, but actually, there's lots of interesting instruction hidden under this. Because the idea is that every mapping corresponds to a digraph. So that is, you have for every position in a word, you make a node. So these 37 positions is where we have 37 nodes. And for every node you just draw an arrow from the node to its value. Since there's N different possible values though, there's N different possible places to point. So, every node has outdegree 1 there's only one place every node can point to. That's its position in the mapping. So 30 points to 18, 29 points to 23, and so forth. But some nodes could be pointed to a lot. That's like 33 is pointed to by 4,14, 19, 28. That appears four times in the mapping. So the sequence of numbers kind of masks this interesting combinatorial structure. And so once you see this structure, then this all kinds of, it breaks up into things that are kind of like trees. Well, they are trees that eventually go to a cycle. So it's a cycle of trees. But there's independent components, too. So natural questions that come up is. Well, what's the probability the things is connected? Or, If it's not connected. What's the average number of connected components? Or how many of the nodes are on cycles? And how many of them are on trees? All these types of questions turn out to be of great interest for important applications. But just as mathematical curiosity it's quite a fascinating structure to get out of a simple idea like an N-word function from an set of integers unto itself. So in order to address those kinds of questions, we'll start with something simpler called Cayley trees. So a Cayley tree is a labeled, rooted, unordered tree. So labeled means all the nodes are labeled. Rooted means that there's one distinguished root. And unordered means we don't consider the order if there's two children of a root. We don't consider the order of the two children to be significant. So there's nine different Cayley trees of three nodes. So these six are all different because of the labels and these three are all different because of the labels. One, two, or three could be at the root. But it doesn't matter what order the sub trees of the root are. Those are called Cayley trees. Now, rather than write out all the possibilities, the short form to do this is to just write the unlabeled trees and then write all the N-words that give those same trees. So, for example 1 1 2, so that's this first tree here. 1 points to 1, 2 points to 1, so that's 1 1. And then 3 points to 2, and so forth. 1, 1, 1, and that's 1, 2 and 3 all point to 1. So that's the N-word, and that's the tree structure that comes out it for all those cases. So that's Cayley trees. So now the answer is the number of Cayley trees, you might have guessed that there's a power going on. It turns out to be N to the N minus 1. But that's not at all an elementary result. We're going to use a technique called Lagrange inversion, eventually, to get to this result, and it's described on the next slide. Lagrange inversion is a classic method for computing a functional inverse. And it's a very important and deep theorem. I'm not going to go into all the ramifications because we use it in a quite as straightforward way. So, for example, if I have a function f(u) = z like f(u) = 0 over 1- u, then, the inverse of that is the function u = g(z). So if I set z = u over 1- u, and solve for u, I get u = z over 1 + z. So that's the inverse. And so, Lagrange inversion's a classical method for computing this, and we'll see how it applies for us. So this is the Lagrange inversion theorem. That in our situation, will be a transfer theorem to get us from a generating function to coefficients for problems where we're counting trees. So what it says is, that if you have a generating function. And so, it's g(z) and it satisfies this equation z = f(g(z)). So it's a little ahead, so we want to compute the inverse with g(z) we wanted to know with f. So if f(0) = 0 and f1(0) has to be non-zero, then g(n) = 1 over n, coefficient of u to n -1, u over f(u) to the n, in the function u over f(u) to the n. And again, we're just going to look at applications of this theorem. So, just for our example, if f(u) is u over (1-u). Then, gn. So u over 1- u. So u over f(u) to the n. So u over f(u), the u's cancel. It's just 1- u to the n. So it says that g sub n = 1 over n coefficient of u to the n- 1. And 1- u to the n, just from the binomial theorem, that's exactly -1 to the n- 1. So, that says that g is sum of -1 to the n, z to the n which is z over 1 + z, which is what we got from algebra. Now you can't always get it from algebra, is the point. You have to use the Lagrange inversion theorem. So in the analytic combinatorics context, we're going to apply this as a transfer theorem and you'll see examples of this. And we'll talk more about it in the context of complex plane in part two. Actually we use as a more general formulation of it, where you can, for any function H of the generating function, you can get the coefficient of z to the n in that and it just includes an extra factor H prime(u). H(u) = u is the basic theorem. So now that's Lagrange inversion theorem and that's the technique that we're going to use to analyze mappings. So now let's look at how it works for binary trees. So for binary trees, we have the standard construction and the OGF equation. So with Lagrange inversion, we can extract coefficients immediately from that equation because it has the form z equals a function. So if we use f(u) = u- u squared for Lagrange inversion. So we want to find the coefficient of z to the N and T(z). And f is that minus that squared. So you use f(u) = u- u squared. So we want to find (u / f(u)) is (1 / 1- u). So coefficient of [z to the N] T(z) is, according to the theorem, 1 / N coefficient of [u to the N- 1] and (1 / 1- u) to the N. And that is easily shown to be that Catalan numbers. So that's one example of an application of Lagrange inversion. So now let's look at Cayley trees. So what we want is the class of labeled, rooted, ordered trees. So we got a word and it has one root and it's labeled. Unordered trees, we don't care about the orders. So with the symbolic method, we just use the construction that says a tree is a root connected to a set of trees. The order doesn't matter, so we use set. So that immediately translate to the EGF equation. These are labeled objects, so we use EGF. It's C(z) = ze to the C(z). That's called the Cayley function, so one that enumerates Cayley trees. So, in other words, z equals C(z) / e to the C(z). So that's used in Lagrange inversion, where the f(u) = u / e to the u. So coefficient of z to the N and C(z) by the Lagrange inversion theorem, we look at u / f(u), which is just e to the u (u / u / e to the u) to the N. So it's the coefficient of [u to the N- 1], 1 / N times the coefficient of [u to the N- 1] and e to the uN, which is N to the N- 1 / N factorial. So the number of Cayley trees is N to the N- 1, and that checks with our small values. So that's a Lagrange inversion to enumerate Cayley trees. Now, that's just trees. Now we can work up to look at more complicated structures like connected components and mappings. Remember, mappings are cycles of trees. So this isn't all the mappings. These are the ones that are just a single connected component. So these are all the possible things that can happen, all the possible connected structures that you can get with three words with three mappings. So, for example, we saw a 1 1 1 or 2 2 2, so that's when they all point to the same thing. But you can get a structure like this where [COUGH] two of them point to each other and so forth. So these words, and so 1 points to 2. Say, this is 1, 1 points to 2, 2 points to 1. Or this would be 1, 1 points to 2, 2 points to 1 and 3 points to 1, and that corresponds to that word. So these are all the ways to label and get that structure. In fact, those are connected, so how many different ways are there to get cycles of Cayley trees? That's what a connected component is. And that turns out to be N to the N times square root of pi / 2N. And the analysis of that is, again, straightforward using the symbolic method and Lagrange inversion. So this is a typical cycle of trees. And, clearly, the construction we're going to use is components of cycle of trees. And then from the symbolic method, just log of 1 / 1- and that is immediately available for Lagrange inversion. Again, we've got f(u) = u / e to the u because that's what the Cayley function does. And then our extra function in the Berman form is H(u) = log of (1 / (1- u)). That's going to immediately give, so H prime(u) = (1 / (1- u)). And then we still have the e to the uN, that's (u / f(u)) to the N. So our number of connected components is 1 / N coefficient of [u to the N- 1] in that formula. And so just doing the convolution, it's N to the k- 1 / K factorial [COUGH] and change N to (N- k). And our coefficient is N factorial times that, and that's our familiar [COUGH] Ramanujan function, which leads to that enumeration result. So that's the number of connected components and mappings, or the probability the component is connected is divide that by N to the N square root of pi / square root of 2N. Connected components and mappings comes directly from symbolic method coupled with Lagrange inversion. And then mappings, how many mappings are there? So that's going to cover all possibilities. And again, what's a mapping? A mapping is a set of cycles of Cayley trees. So it's going to be e to the log of 1 / 1- C(z), which is just 1 / 1- C(z). And that one, we can get with the extended Lagrange inversion with our H function = 1 / (1- u). If you do the map, H prime(u) = 1 / (1- u) squared, so it's coefficient of [u to the N- 1] of 1 / N and 1 / (1- u) squared e to the uN. You do that convolution and this time, the sums collapse, it just works out. (N- k) from 1 / (1- u) squared N to the k- 1 / k factorial from e to the uN. And then we just get two sums and they all cancel except for the last term N to the N / N factorial. So the number of mappings is N to the N as we expected from the trivial argument. So sure there's a trivial argument that helps us the number of mappings. But this analysis gives the entire structure that we can use for analyzing all sorts of properties. And we'll go into the details later on. Just for example in interesting property of these functions, something called a rho length. So, the rho length of a function. So if we start at a given point, and just apply the function, say you have a function like x squared + 1 mod 99. So, 3 goes to 10. 10, 100 + 1, 101 mod 99 is 2. And In that, square that, and that's 5, and so forth. You eventually get to a point where you hit a cycle. So that's called a rho length, the number of times you reiterate the function until it finally repeats. Now, so in the mapping wherever you start you always going to wind up in a cycle. So, there is rho length associated with each point in the mapping. This is a mapping where we have a formula to tell us where it is. But random mapping is still the same thing. One thing to think about is what about an algorithm to compute the rho length. It's kind of a fun problem. You could say well I'll just use the symbol table, I'll keep track of all the values I've computed and then that way I'll know when I get a repeated value. But in practice you can't do that because we talk about in real applications we're doing this. For huge numbers, like hundred digit numbers, and there's no way to have enough memory to keep all the possible values. So, what do you do? Well, there's a famous method due to Floyd. Which is a Tortoise and Hare algorithm, where you keep two variables. One that iterates the function just once and the other one iterates it twice. So, for example, a and b start at the same place at time t = 0. And we iterate a by 1 and b by 2 and then iterate a by 1 and b by 2. So b is going to go around the cycle. And eventually they catch up. And it's not difficult to see that eventually they're all going to catch up. And when they do, actually, the rho length of starting at that point, is between t and 2t if t is the number of times that you have to go to get it to match. So that's an interesting, and that doesn't use any extra memory. It's just comparing those two variables. So that's computing the rho length. So, with mappings, again, starting at every point, you've got a row length and that's a parameter that's interesting to study. In this other tail length. That's how long until you hit the cycle. And again number of components, number of trees, and so forth. Now, using the same method of construction and using bi-variate exponential generated functions It turns out that, just to give an example, like number of components. Mapping is a set of cycles of trees. But we mark the cycles, and that'll tell us the number of components. There's one for each cycle. So immediately, we get the EGF equation, 1/1- C z can be u. And then we can work with that equation to answer questions like what's the average number of components. Or if you're doing number of trees, then it's a set of cycles of trees then you just mark the trees, then you get this other function. And we'll talk about this analysis in more detail in part two. But for now just want to mode way be study of mappings, and its works out be actually without premature work we can get all this properties of mappings. So for example the expected word link in real mapping is about square Pi and two. So why is all this relevant? Well, here is an actual application where it matters. This is a famous method for factoring an integer, a huge integer. It's called Pollard's Method, and what it does is it iterates a random quadratic function to find a cycle. It's pretty much like the function there that I just talked about. We take f of x equals x squared plus c until finding a cycle. Now we do it like with folds where we take two variables and get rid of once for one of the variables and get rid of twice for the other. We use a random value of c at a random starting point. And keep going until this particular condition is satisfied having to do with the GCD. When it's done you get a factor out. It's quite an amazing algorithm. This is just an example. That is doing the same thing as fluid algorithm done and when the GCD of these things is not one then you found a factor. So why does it work? Well, it's actually not too difficult to see how it works if you know number theory although it's definitely magic if you don't. That's not really the point of why I want to bring it up now. The question is how many iterations does Pollard's algorithm take, and well one thing that seems to do is to assume that this function is not a random mapping, but since you're taking a random c and a random starting point. Maybe it's got the same characteristics as a random mapping. And it's conjectured, actually, that the random quadratic function of this type is asymptotically equivalent to a random mapping. And in a random mapping, the rho length is square root of pi N over 2. So you can factor a number, you can factor a number N. In square root of N cycles, which is a lot faster than trying every factor. And Pollard actually used this method to factor huge integers a while ago, and it's typical of the kind of thing that people are trying to do in cryptography nowadays, is that studied properties of these kinds of functions. Analytic combinatorics and properties of mappings plays a role in this kind of research. So I wanted to end with a real application like that and end with mappings. They are quite fascinating combinatorial structures.
