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.