Now we're going to talk about the analysis of random mapping. this is something we've been promising for a while and actually it uses, a lot of the things, pretty much everything we've talked about, so far. For the analysis it's a very elegant and compelling application of analytic combinatorics. So mapping is a function from the set of integers, from 1 to n, unto itself. this is from, a lecture two. and we can, represent every map thing with a diagraph, where every node has out degree one. it goes, there's an arrow from every node to some other node. and the N degree could be anything from zero to N. In some mapping, some, the mapping divides up into components and the components are cycles, or they're cycles of labeled trees. And the, lots of applications where we're interested in studying properties of mappings and, natural questions that come up are, how many different components are there on average in a random mapping? how many of the nodes are on cycles and how many are on trees and so forth and several other parameters that come up. And these are all handled in fairly straightforward manner, with the schemas that we've been considering. so first question is enumeration, how many mappings are there of length N. and we talked about this in lecture two. in one sense it's easy. You're mapping N images onto themself for each of the N. position, needs to be in nods. As in impossibilities as of where good points, so it's into the end. but, the internal structure, is of interest in plenty of applications, so this is another way, to, a, break out the number of mappings. And we're going to let it come to torks. We're going to take a look at the structure and that also allows us to analyze every values of perimeters. And so we looked at this basic setup in lecture two. it starts with trees, Kaylee trees, labeled rooted unordered trees.A Kaylee tree is a node and a set of trees. Root in the set of trees. and that translates by the symbolic method immediately to c of z equals zc of z. a component in a mapping is a cycle of trees. So, y equals the cycle of trees, where c is the class of trees. So, y is log of 1 over 1 minus c of z. Where c of z is defined that way. And then a mapping is a set of cycles of trees. It's a set of mapping components. and that translates to the EGF equation, e to the log of one over one minus c of z, or one over one minus c of z. so that's the basic structure of the symbolic method for mappings, and now we're going to see how that has implications for the analysis of the enumeration of each one of these items. and, and for enumeration of parameters of mapping. so this is from earlier in this lecture, we just did this one that's a Cayley's tree, labeled ordered trees. We went from the construction to the generating function. And then it's a simple variety of trees, so we went to immediatly to the coefficient asymptotics. that was our last example of a simple variety of trees. This exactly this class C. but, remember at the beginning of the lecture, I pointed out that we not only can get coefficient asymptotics from singularity analysis. We can also get approximation to the function. so, I've been leaving this off but that's, in theorem we get approximation to the function. it's lambda minus the same constant, times squared one minus z [UNKNOWN]. so, in this case where lambda is one and they're all e, it says that the generating function for Coyley Trees is [UNKNOWN] to. at 1 over e, which is where the near single error of the origin is. That's asymptotic to 1 minus square root of 2, square root of 1 minus ez. And so, we can make use of that approximation later on in the analysis. So, for example, we want to know the number of cycles of trees. that's the components in a mapping. the generating function equation we get is immediately log of 1 over 1 minus c of z. But the last slide c of z is asymptotic to 1 minus root 2, square root of 1 minus c of z. 1 minus that is root 2 square root of 1 minus ez. so that comes out to half log of 1 minus ez minus log root 2. just plugging that in so that's approximation for the generating function for the number of mapping components. but this one is just standard scale. Just as log 1 over 1 minus c z is e to the n over n. So that immediately gives the asymptotics of the coefficients, or number of cycles in trees is e to the n over 2 n. or another way to look at that is to apply Stirling's formula and get square root of Pi over 2 and then to the N. so then there's two different expressions for, for that, or that's factoring in the N factorial to get the number of different mapping components of size N. So that cycles of trees, and now we want the class of all mappings. Mapping is a set of cycles of trees. So that's e to the y of z. y of z on the previous slide, we show that y of z is [UNKNOWN] to half log, 1 over 1 minus z, e z minus log of square root of 2. So now we have e to the log. That's exp log. so, our theorem for exp log labelled sets says if we're taking e to something that can be approximated to a log, we just have to know the constants. Coefficient of the log is one half, z over row, that's 1 over e. And beta is minus log 2. So those three values, plug those in, and we immediately get the asymptotics of the class of all mappings. Alpha equals one half, beta equals log squared or 2, row equals 1 over e. and we get the, number of mappings is asymptotic to n factorial e to the n over square root of 2 pi n, which is Stirling's Equation in another form, because it, applying Stirling just, leaves the n to the n. and that's what we're looking for in the first place. even the tree simple transfers from analytic combinatorics that seems like a lot of work to get down to in to the end. but it tells us the entire structure. And we can extend this to similar problems as well. I just want to give an overview of what that structure looks like. just a reminder again. We started with Cayley trees. So we applied our simple variety of trees, schema, and I had to get the, get that one, and then for components in mappings, we plugged them at approximation and used this standard scale. and then to do mappings themselves we use exp-log. So three different transfers schemas to get down to the answer for mappings. and so they all have, have their uses in, in this problem. But more generally if we want to look at problems like what's the average number of components, in random mapping. Or how many of the nodes are on, on cycles, in average. use their calculations for the small examples. then, we can get those, just by, the same process just, extending the transcript there slightly. Well components come for free because we have the corrolary to exp log saying that you have an exp log setup, the number of components is alpha log n. we had alpha equals a half, so average number of components in a random mapping is one half log n. again, it comes immediately through by the same process that we use for a simple problem like permutations. or nodes on cycles where we can use [UNKNOWN] generating functions, mark the nodes on cycles with U, so then we get a [UNKNOWN] generating function X block one over one minus U. and now we can put in to get the expected number of nodes and cycles we have to differentiate with respect to u, and evaluate at 1, so that gives us an expression in terms of the generating function for a Cayley trees. But now, at this point, with singualrity analysis, we had that approximation for that generating function so we can plug in that approximation. So C of Z equals one minus square root of two squared one minus CZ, one minus C of Z equals just that and then if you square it, you get two times one minus CZ. And C of Z over one minus C of Z square [UNKNOWN] to one half [UNKNOWN]. Ez. So, you can check that, but that's not too difficult. So that gives us, an approximation for, the, generating function, for, the expected number of nodes on cycles. So I might want to get the coefficient of z to the n on that, but that's just an expansion. It's just e to n over n to the n. And then applying applying sterling formulas the, the pi comes back pi or the, pi over square root of two pi comes back. And so the average number of nodes and cycles is square root of pi over you know, over 2. very straight forward calculations based on singularity analysis. and this, this graph for example, the, it, it predicts that there'd 12.5 nodes and cycles and actually there's 9 in that but for bigger graphs it'll be more accurate. these estimates are accurate to one over n. So and we can get more terms if we wanted because everything that we do is extended and sendable to any acitotic accuracy. So that's the use of singularity analysis to study mappings and their characteristics.
