Symbolic Method for Labelled Classes

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

19 notes

Princeton University

Analytic Combinatorics

19 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

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.

Télécharger dans l'App Store

Disponible sur Google Play