0:03

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.

Â 1:20

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.

Â 2:15

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?

Â 2:31

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.

Â 3:27

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.

Â 4:01

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.

Â 5:52

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.

Â 7:16

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.

Â 8:31

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.

Â 9:15

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.

Â 9:48

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.

Â 10:12

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.

Â 11:00

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.

Â 11:42

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.

Â 12:16

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.

Â 12:36

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.

Â 13:24

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.

Â 14:46

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.

Â 15:05

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.

Â 16:57

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.

Â 17:59

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.

Â 18:23

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.

Â 18:52

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.

Â 19:09

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.

Â 19:30

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.

Â 20:30

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.

Â 21:42

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,

Â 22:02

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.

Â 22:47

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.

Â