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.
Mappings
Loading...
En provenance du cours de Princeton University
Analytic Combinatorics
19 notes
À 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.
Rencontrer les enseignants
Robert SedgewickWilliam 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.
© 2018 Coursera Inc. Tous droits réservés.
