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.