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.
Symbolic Method for Labelled Classes
Loading...
En provenance du cours de Princeton University
Analytic Combinatorics
15 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
So next, we're going to look at the, the full set of, basic operations that we're
going to use to make labeled classes, and the symbolic method, which is the
association from those constructions to generating function equations.
And again, it very much parallels what we did for unlabeled classes in this other
setting. So, we're going to use a disjoint union
operation, the labeled product operation that I just described.
and then we can build up a class by taking a sequence of objects from another
class, or a set or a cycle of objects. In those correspond to the permutations
earns and cycles of basic objects that I talked about as basic examples.
and so, the semantics is very natural. the disjoint union is just copies of
objects, a pair that's copy of objects from A and B.
Labeled product is take one from A, one from B, relabel them in all consistent
ways. Sequence is a sequence of objects, set is
a set, and cycle is a cyclic sequence. and those are very natural and easy to
see when we do examples. more important, we have the symbolic
method which, if the, we have the exponential generating functions, A of z
and B of z, for the combinatorial classes that we're using as part of the
construction. Then the construction immediately gives
us an equation for the exponential generating function.
Same as for unlabeled if you take the disjoint union and have disjoint copies
of objects from A and B, then the EGF is sum.
And we'll look at the proof of this which is quite natural.
For star product, it's the product. And again, that's by design.
in the proof which we'll look at is quite natural, even in the labelled setting.
for sequence if you have a sequence of length k it's just A of z to the k just
by extension of the product. if you have a sequence of any length,
then it's 1 over 1 minus and again we'll look at the proof of this.
for set, it's A of z to the k over k factorial or for a set of any size it's e
to the A of z. and for cycle, if it's a k cycle, it
saves you to the k over k and cycle of any length that's log of 1 over 1 of a
minus z. These are very natural and we will show
the proofs in a minute. Just as an exercise it's wise to look at
this star product transfer theorem for, for the small example that I showed
before. whereas 1, 2 times 1, 2, 3 is equal to
those ten objects. How does that work in terms of the
exponential generating functions? Well, the exponential generating function
for 1, 2 is just z squared over 2 factorials.
Just one object. And for 1, 3, 2, it's z cubed over 3
factorial. What's the exponential generating
function for this combinatorial class on the left?
Well, there's ten of them and they have five objects, so that's z to the 5th over
5 factorial. so, 10 times z to the 5th over 5
factorial. that's, five factorial's 120, so that's z
to the fifth over 12. And that's B of z times C of z, exactly
as the transfer theorem says. You have the EGF for uh,[COUGH] the two
classes, and you star product them, the EGF for the result is the product of the
two EGFs exponential generating functions.
And so, that is just to check for this small example in it works in, in general.
and again, the basic instructions that I talked about in the set up are just
applying of this, these basic theorems. unearned if the set of objects, cycle is
a sequence, sequence of objects, and permutation is a linear sequence of
objects and those are our examples. And the transfer theorems immediately
give us the generating functions without having to count.
they EGF for earns, is e to the z. It's a set of objects, it's a single
object, EGF is g, and the theorem says you take e to that power for sets.
For cycles, it's log of 1 over 1 minus z, directly from the transfer theorem.
We don't have to reason about counting them.
and for premutations, it's 1 over 1 minus z, again directly from the transfer
theorem. Then we can extract coefficients from
those generating functions to get the counting sequences.
And again, of course, this checks for the basic instructions but that's the same
method that we're going to use for any kind of combinatorial class.
the, specify the construction use the transfer theorem to get a generating
function, and then, extract information about the coefficient from the generating
function. so, here's the proof of the transfer
theorems. and I'm not going to dwell on these.
they're quite straightforward and they're very similar to what we did for unlabeled
classes in the last lecture. for this joint union if you want to the
EGF for A plus B. if there's item in A plus B, then as a
term z to the size of that item, the size of that item factorial.
That item had to come from either A or B, so we can separate the terms into As and
Bs, and that's just A of z, B of z. for the star operation, it's it's more
complicated. As we did in the small example we simply
choose some set of labels for the object that we took from A.
There's A plus B choose A possibilities for that.
and then the terms are z to the the size of A plus B, A plus B factorial.
And if we group the ones for A and one for B, the A plus B factorials cancel
out, so that the ones from A and ones from B are independent, just as they were
for the unlabeled classes, which gives the product.
again, it's extremely straightforward if we reason just based on the pairs of
objects. And that one is the key operation the
others follow immediately just from the simple equations on the generating
functions. So, for example A of z to the k.
so that's the number of k sequences of size N, z to the N over N factorial.
so from the, just extending the product operation that's the generating function
for that, is for taking a sequence of k items from an object, is A of z to the
kth power. so it's just the product operation k
times. but that same end if you sequence of any
length, then you're going to be a sequence of size 0 plus 1 plus 2, and so
forth. and so that's just 1 over 1 minus A of z.
so that all directly follows simply from the product operation.
now for cycles, if you take all the k sequences of size N and add them up, then
you're going to see each cycle k times. So, A to the z to the k over k is, the
generating function for the number of k cycles of size N.
so that's just an argument based on algebra from this generating function
equation. k cycle of, of objects from class A is A
z to the k over k. And again, a cycle of any length, you
just add those all up, and that's the natural log of 1 over 1 minus A of z.
And again, the same kind of argument, if you take all the sequences of size N,
you're going to see each set, k set, k factorial times.
So that means A to the z to the k over k factorial is the generating function for
the k sets of size N. k sets of size N, sorry, the k sets from
A is A to the z to the k over k facotiral is the generating function for that.
And again, summing those for all possible k gives the e to the A to the z for a set
of items from A. So those are simple proofs, actually, but
we won't need to consider them again, because the transfer theorems are so easy
and so direct. so and, and again this is a repeat from
the last lecture. But it's even more true for, well
similarly true for labeled objects. The simple constructs that I've shown are
quite elementary and confirm our intuition.
but we can use the constructions to build up compound constructs in many different
ways. And as we'll see, they give us a
classical combinatorial objects of all sorts and expose their underlying
structure. And we can go even further with
variations on the classical objects with different restrictions.
And we can get quite complex combinatorial constructions that maybe we
need in modeling some real world problem. but we treat in precisely the same way as
the elementary ones and we get the result of a generating function equation that it
would be very, might be very difficult or complicated to otherwise analyze.
Of course, there's some way, because underlying it all are the simple
combinatorial equations that I showed but this approach is going to suppress a
great huge amount of the detail. So we'll see this , in look at this in
some examples right away for permutations.
so a permutation is set of cycles. and that a well known in combinatorics
and it's a lot of detail of this. In part one, lecture five, if you want to
go look at detail. So you can write a permutation as, this
is a permutation of 16 elements. It's just an ordering of the 16 elements.
If you think of it as a mapping, say I want to go from the entry 10 and 4th
position, it means I go from 4 to 10. And I look at 10, and that goes to 6, and
6 goes to 15, 15 goes to 4, that's the cycle.
and so, the elements, starting anywhere, you can create a cycle, and then give a
correspondence between permutation and a set of cycles.
So, that's a, a set of cycles representation of this permutation.
that's a well-known combinatorial bijection.
But from the point of view of analytic combinatorics we can see that the counts
of these sets are equal. Or we can understand better say, the
structure of the cycles and permutations using combinatorial construction.
so have, here's just an alternate way to use combinatorial constructions to count
permutations that's we were talking about.
Permuation is a sequence of labeled atoms.
It's generating functions 1 over 1 minus z by the transfer.
And if you pick out coefficient of z, you get the number of permutations.
But say we didn't know the bijection and we want to count sets of cycles.
Well then, we could use the construction that p star, it's really the same as P is
a set of cycles of combinatorics of of atoms.
P is a set of cycles of atoms. Then the transfer theorem immediately
says that the generating function for that class is cycles of atoms as log of 1
over 1 minus z, and sets of that is e to that power.
Well, e to the log of 1 over 1 minus e is just 1 over 1 minus z.
So that's a different way of getting to the generating function.
But we'll see that we can modify this argument to tell us about the cycle
structure of permutations in more detail. and any way, we get the same result.
So let's see a variation of that, and a famous variation of that is called
derangements. and there's many ways to look at it, and
again, there's lots of amusing stories about this in the lecture in part one on
permutations on analytic combinatorics. So if you have n students and they throw
their hats in the air and each catch a random hat, what's the probability that
nobody get their own hat back? Well, that's called a derangement.
If we count the permutations that have no singleton cycles then that's, and divide
that by the total number of permutations, we get that probability.
So and enumerating derangements is a simple modification of the derivation I
just did for permutations. How many permutations have no singleton
cycles? Well, we construct them by taking a set
of cycles that are bigger than size 1. derangements are permutations with no
singleton cycles and that then is immediately reflected in that that
construction. Cycles of size 1 bigger than 1 it's, is
the generating function for that is z squared over 2 plus z squared over 3 plus
z 4th over 4 plus so forth. It's a natural log of 1 over 1 minus z,
but leaving off the first term, the z for size 1.
Or it's, another way to look at it is it's e to the log of 1 over 1 minus z
minus z, subtract off the singleton cycles.
so the generating function for derangements is e to the minus z over 1
minus z. now we can extract coefficients from
that, now in, with a little bit of analysis, show that it's asymptotic to 1
over e. we'll show how to do this in a uniform
way later on in the course, but anyway, for this case, it's not hard to convince
yourself that the coefficient is asymptotic to 1 over e.
and that solves the problem that probability that nobody gets their own
hat back is about 36% that's a classic problem in combinatorics.
From the standpoint of this course what we want to take away from that is, the
simple modification of a basic construction, gives us an easy answer to
this practical problem and it generalizes.
so, how many, how many permutations have no cycles of length less than or equal to
M. so that just generalizes the previous
argument to put bigger than M there, and just leave off the smaller cycles.
and that's e to the log of 1 over 1 minus z, subtracting off all the terms up to N.
or it's e, rather complicated generating function, and now, extracting
coefficients from that, using classical methods might be a challenge.
so that's for the second part of the class to see how we get asymptotic of
coefficients of functions like that. But for this part taking the construction
and getting an equation on the generating function is a very simple process.
or another uh,[COUGH] flavor of permutations that people study are called
involutions. How many permutations have no cycles of
length bigger than two? They're only one cycles or two cycles
well, it's a set of one cycles per two cycles and the generating function is e
to the z squared over 2. As we'll see, these two things are
completely different analytically. and require completely different
techniques for understanding asymptotics of coefficients.
but from the formal standpoint of the symbolic method they're quite natural.
and so we can have generalized involutions where we go up to size m and
so forth. so that's an example how a simple
commonitorial.g construction with variations can lead us, not only to a
study of commonitorial objects that more close that mirror situations we see in
the real world. but also give us immediately, through the
symbolic method generating function equation.
so we start with set of cycles of, of atoms and then we look at the
arrangements, which is just the modification of that construction or
involution where they are only built from size 1 or 2.
We can generalize it in both ways to look at all cycles bigger than a certain size
or no cycle bigger than a certain size, or actually, we can have arbitrary cycle
length, constraints, and still get a generating function equation.
That's an example of the symbolic method used to derive generating function
equations by simple modifications a standard paradigm.
And an introduction to the symbolic method for labeled objects itself and
we're going to look at many other examples.
and there's plenty of other things that you can do with permutations.
what about the ones with exactly N cycles?
Well, that's a set of size M of cycles. And so, that's the generating function
for that. And you can imagine many other types of
modifications of this. so that's an introduction to the symbolic
method for labelled classes.
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.
