0:00

Now we're going to finish up our, our study of labeled combinatorial classes by

Â talking about mappings. so a mapping is a very simple concept.

Â A mapping is an inward of length n. so it's a function from the integers one

Â through n onto itself. so, we just, list, all possibilities.

Â and it's pretty clear that the number of mappings is going to be, N to the n, for

Â every, position, we can assign anyone of n different numbers since N to the n.

Â Now that's simple enough. But actually there's the underlying

Â structure that's fascinating and related to and arrising in numerous applications.

Â Mapping as a function, from the set of integers from 1 to n onto itself.

Â And so here's an example of a long mapping, where I had the numbers 1

Â through 37 and then down below I have the numbers 1 through 37 and they can appear

Â multiple times. That's a mapping.

Â Each one just has to be some number between 1 and 37.

Â Now what's interesting is there's you can use a directed graph structure, also, to

Â describe mappings. And they, expose the commonatorics of

Â what's going on maybe better than the tabular structure.

Â So for example, 27 goes to 20. and then 20 goes to 9.

Â and then 9 goes to 26 and 26 goes to 1 and 1 goes to 9.

Â so this is a special case of the sets of cycles that we had for permutation.

Â But it sets of more complicated structures that this directed graph

Â illustrates. so you have, there's natural questions

Â that arise. And that are actually important in, in

Â applications. so like what's the probability that it's

Â connected? or how many different components are

Â there? how many nodes are on cycles and how many

Â are on trees? and then there's parameters of mappings

Â that we'll talk about next time is, like what's the average time it takes to get

Â from a node to its cycle? What's the average size of the cycle?

Â All of these questions are of practical interest and [COUGH] analytic

Â combinatorics, again, handles them all in a uniform way.

Â So let's just look at a numeration, how many mappings are there of length end.

Â Again, if we go like we did for trees we can look at different ways for labeling

Â the different structures that might come out.

Â And again, now there's definitely plenty of comlications in the number of

Â different structures there are. there's only one way to label that one

Â just one, two, three. or another way to look at it is just list

Â out all the 27 mappings, and then see what the structure looks like.

Â So, one, one, two. So that means one points to itself.

Â two points to one. And three points to two.

Â But that's also the same as three, two, two.

Â that's where two points to itself and three points to two and one points to

Â three. So those are all the different ways to

Â label that structure. And there's six of em, six of em, two of

Â em. And again, this complicated labeling and

Â this complicated set of structures adds up to this simple result, n to the n.

Â My correspondence with n words but this internal structure is definitely of

Â interest. So with analytic commonatorics we're

Â going to be able to take that apart and understand properties of the structure

Â which is important in applications. now in order to do this we're going to

Â need a powerful tool known as Lagrange inversion.

Â and it actually is useful for the study of of any tree structure, and it's a very

Â deep theorem, it has many applications in mathematics.

Â we're going to use it in a, in a, in a, a pretty straightforward way, but anyway

Â it's necessary to state it. I'm going to leave out the proof, because

Â it's best understood via more advanced techniques than what we're going to cover

Â in this course. but anyway, here's a, here's a statement

Â of the so-called Lagrange inversion theorem.

Â So it's, it's, the idea is it's about the inverse of a function.

Â so I have a function f of u equals z. then the, it's inverse is the function u

Â equals g of z. So for example if f of u equals u over 1

Â minus u, then solve for u and that's g of z equals z over 1 minus z is it's

Â inverse. So the lagrange inversion theorem says

Â that it, it gives away to get the coefficience of g from the form of f.

Â So it says that if you have a generating function that satisfies the equation z

Â equals f of g of z. so that's the, inverse, definition.

Â in these conditions that f is zero and f prime of zero is zero.

Â And if f prime of zero is not zero then, then the coefficient g sub n is 1 over n,

Â time the coefficient of u to the n minus 1 and u over f of u to the nth power.

Â so and that's what it is. so in our simple example, where f of u

Â equals u over 1 minus u. Then the theorem says that the

Â anti-coefficient, the generating function for g of z.

Â Is one over n, coefficient of u n minus one, in one minus u to the n, because u

Â over u over one minus u is one minus u, one minus u to the n.

Â Coefficient of u to the n minus one, that is minus one to the n times minus one to

Â the n minus one, and divide by n we get minus one to the n minus one.

Â And that's exactly what g of z is, g over 1 plus z.

Â so you can study this and, and learn about inverses, but really we're going to

Â be applying this theorem in pretty much a cook book fashion symbolically, just like

Â this. so, from the point of view of analytic

Â commonotorics, it's an analytic transfer theorem that gives us coefficients once

Â we know a generating function, 'cuz in recursive structures like mappings and

Â trees, we often encountered generating function equations like this.

Â in fact, we use a, a more general formulation called the Burmann form of

Â the Lagrange inversion theorem and that's if we forgot a, another function Uh,H of

Â u, and you want the coefficient of H of g of z, then we put in H prime, and, and

Â it's just generalizing the basic theorem from H of u equals u.

Â so this is the form that we're really going to use for mapping.

Â and again, it's, this is a, a deep and wonderful theorem that I don't have time

Â to do anything more than Uh,[UNKNOWN] so that you can understand how we extract

Â coefficients. so, just as a classic application for

Â catalan numbers, so this is with ogs that we did last time.

Â binary tree is a node or two binary trees.

Â I'll just count by external nodes so we have that OGF equation.

Â so rewriting that is z equals t of z minus t of z squared.

Â So that z on the left hand side, that makes this, a candidate for a Lagrange

Â inversion, so, the theorem says if we want the coefficient of z to the n in t

Â of z, we're just going to take, f of u be u minus u squared.

Â So then we got z equals f of z, f of g of z.

Â so, u minus u squared, t of z minus t of z squared.

Â so we took f of u equals u minus u squared.

Â So we want u over f of u. So that's u over u minus u squared.

Â That's one over one minus u. So, we have co-efficient of u to the n

Â minus one and one over one minus u to the n.

Â and, just, use, the standard generating function for one over one minus z to the

Â n we get the Catalina numbers out. So that's a classic application of a

Â Lagrange inversion. and we can use it for other types of tree

Â structures, we get other types of f of u in the same method, is going to work, and

Â we'll look at it from a general point of view later on.

Â but now let's look at Cayley trees in mappings.

Â So, so Cayley trees are labelled rooted unordered trees.

Â so they're special case of mappings where every node points to just one node.

Â And there's one root, and it's connected. so, the construction is simple.

Â a Cayley tree, is a tree, connected to a set of trees.

Â the transfer theorem then gives us, immediately, C of z equals z e to the C

Â of z. That's the exponential generating

Â function for Cayley trees, labeled root of unordered trees.

Â 10:16

And so that means that z equals c of z over e to the c of z.

Â So that means we can apply Lagrange inversion with f of u equals u over e to

Â the u. c of z over e to the c of v.

Â And so, that's Lagrange inversion. U over e to the u.

Â U over u over e to the u is e to the u, so the number, coefficient of z to the n

Â is 1 over n, coefficient u to the n minus 1 in that.

Â that's coefficient u to the n minus 1 and e to the un, and well, e to the un,

Â that's some of k factorial, you went to the k over k factorial, coefficient n

Â minus 1, in that is n to the n minus 1. So, the, number of Cayley trees with n

Â nodes is n to the n minus 1. So that's a direct proof with analytic

Â combinatorics. Now it does depend on Lagrange's

Â inversion, but Lagrange's inversion is a very general tool that we can use in this

Â same way for many similar problems. So that's, Cayley trees.

Â now it suggests a some kind of bijection between Cayley trees and words with n

Â minus or say with, in mappings with a constraint on it, but that's actually one

Â of the classic problems in commonatorics is to find a simple bijection.

Â Okay, so now what about mappings? Well let's move one step up.

Â so a mapping is got cycles of Cayley trees.

Â So that is you have a Cayley tree and, and then maybe the root note is on a

Â cycle or maybe it's a single cycle of itself.

Â so that's, connected components in mapping.

Â So, or this is how many cycles of Cayley trees are there.

Â And so these are just one connected component.

Â Those are the mappings that have just one connected component, so there's 1 of size

Â 1, 3 of of size 2, and 17 of size 3. so that's, labeled cycles of trees and

Â those are all the ways to label that and, and so forth.

Â so the answer to that is more complicated.

Â and so let's look at it from the standpoint of analytic commonotorics.

Â So here's a cycle of Cayley trees. You take a cycle and then take a Cayley

Â tree going into any element on the cycle. So that's just an example, it's a special

Â case of a mapping. but the construction is simple.

Â A component is a cycle of Cayley trees, and then the transfer to generating

Â functions is simple. the exponential generating function for

Â cycles of Cayley trees is log of 1 over 1 minus C of z, where C of z is the

Â exponential generating function for Cayley trees.

Â Now, what about extracting coefficients? Well here's where the Berman form of

Â Lagrange inversion comes in. We still get to use u over e to the u,

Â but now we have this other function h of u which in this case is log of 1 over 1

Â minus. So, coefficient of z to the n, in log of

Â 1 over 1 minus c of z, where c of z equals u over e to the u, you just plug

Â into the formula and take the der-, so h of u is log over 1 over 1 minus u.

Â We're supposed to use h prime, so that's 1 over 1 minus u and then the u over f of

Â u to the n is e to the u n, just as before.

Â So to find the number of cycles of Cayley trees, its coefficient is z to the n and,

Â and y of z is one oven n coefficient u to the n minus one in that function.

Â and that one is a convolution because you've gone one over one minus u times u

Â to the un, so it works out to that convolution, and then this is just

Â changing n to n minus k, and then the thing that we want is N factorial times

Â coefficient z to the n and y of z. that comes out to this expression here.

Â Hm, and this is a well-known function known as the Ramanujan q function and you

Â can look in part one of the course to where we talk about the asymptotics of

Â that function and we'll also talk about asymptotics of this again.

Â when we get to complex asymptotics in the second part of, of this course.

Â so this, this problem doesn't have so, so simple an answer, in, but, it indicates,

Â the structure that lies, underneath this. and then what we really want to finish

Â the job is the number of mappings, how many different mappings are there?

Â A mapping is a set of cycles of Cayley trees, couldn't be simpler.

Â and then the equation is A cycle of Caylee trees is log one over one minus a

Â set of those is e to that power, so we just get one over one minus c of z.

Â Again that's ripe for use of a Berman form where now we use the h function as 1

Â over 1 minus u, and then f of u equals u over u as before.

Â So now the dif, derivative of h is 1 over 1 minus u squared so it's the same as on

Â the previous slide except we have a 1 over 1 minus u squared times u to the n.

Â and then if we do the convolution that time on this one then we get seems like a

Â slightly different form of it. but actually this one kind of telescopes

Â and gets to the answer n to the n over n factorial.

Â so the end result is the number of sets of cycles of Cali trees is just n to the

Â n. Now quite surprising that we get down to

Â that simple result. But we have a clear explanation,

Â explanation of all this structure through the analytic combinatorial.

Â And that's extremely important when we come to analyzing parameters of these

Â structures, that would be the subject of the next lecture.

Â So, that's an introduction to, mappings, using analytic combinatorics.

Â