Mappings

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

22 notes

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Princeton University

Analytic Combinatorics

22 notes

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Labelled Structures and EGFs

This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.

Symbolic Method for Labelled Classes 18:36

Words and Strings 12:21

Labelled trees 15:25

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

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.

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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play