0:03

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.

8:13

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.