Basics

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

Today we're going to talk about labelled combinatorial structures which we use

exponential generating functions to analyze.

Again, we're going to have a set of combinatorial constructions that we can

use, both to specify the structures and to immediately transfer to equations on

generated functions. this is the in the overview, this is the

second lecture on analytic combinatorics from the symbolic method.

and again, we're going to follow the same general approach that we did for

unlabeled structures and ordinary generating functions, where we have a

specification that's automatically turned into a generation function equation and

then later in the second half of the course we'll talk about turning those

generating function equations into the asymptotic estimates that we're looking

for. Now I want to give the same warning I

gave at the beginning of the last lecture.

quite a bit of this lecture is a quick review of material that we.

Went through in much more detail in Part one of the Analytic Combinatorics Course.

So one consequence of that is this lecture's a little bit longer than usual.

If you took Analytic Combinatorics Part one, and are bored because you understand

everything, that's great. Just fast forward through.

there's some new material on labeled trees and then do the exercises, or use

this as an opportunity to review the material.

if you're starting with this course, and you find that things are moving too fast

you can always go and see some details and motivating applications, in the

earlier course. okay, so let's talk about the basics of

labelled structures. so the idea is that, objects in labelled

combinatorial classes are composed of atoms and if there's N atoms, they're

labelled the integers one through N. So for unlabelled objects there had to be

a difference in structure for the objects to be different.

for labelled objects we add the extra constrains that it's the way that their

label makes for different objects. So these are two different labeled

objects because the labels go in different order around the square.

You can't transform one into the other. Where these are different labeled objects

because the one without degree three has got a different label in each of the

cases. So there's many more possibilities for

labeled objects. and as we'll see, that's why we use

exponential generating functions instead of ordinary generating functions.

So here's an example. Cycles of labeled atoms.

How many cycles of labeled atoms are there?

Well, you, you make a cycle, so here's a cycle of four labeled atoms, and you fix

one item, say say the four, then You have all permutations of the remaining n minus

one items make a different labeled object.

So, it's easy to see that the number of different cycles of labelled atoms is n

minus 1 factorial. so, but then we can look at a more

complicated example. How many unordered pairs of labelled

cycles of size n are there? so there's three different unordered

pairs of label cycles of size N. you got one, so it's a pair, so one of

them has one object and the other one has two.

there's Now you can pick one of the three labels for the one that has one object.

And then, there's only one way to label the one that has two objects.

So there's a total of three different, unordered pairs of labeled cycles of size

n. for four, there's 11 different, you can

pick, you can have one in three, you can label the one object any one of, the four

ways. but then the cycle that has three objects

can be in either orientation. They can be two, three, four or two,

four, three, on the top example. so that makes, eight, or you can have 2 a

pair of cycles of size 2 each, and then there's three different ways to label

them essentially by choosing out of the four the three different possibilities.

And remember it's an unordered pair. So 1, 2 in the left and 3,4 in a right

its the same object as 3,4 in left when 2 in right .

So that's eleven for four and how many for five and the answer is that it turns

out to be the sterling numbers of the second kind and we will talk about that

probably in the next lecture. Okay, so here's the basic definitions

that we're going to work with, and these correspond precisely to the basic

definitions that we used for unlabelled classes.

The first, we say a set of n items is said to be labelled if they can be

distinguished from one another And without any loss of generality we use the

labels 1 to n to refer to the to the atoms.

So a labelled combintorial class is a set of objects build from labelled atoms and

also is an associated size function. Again, just as before with unlabelled

classes. So we use exponential generating

functions and we associate with combinatorial labelled classes, and

that's just a formal power series. Reads a variable z, the function a of z.

It's the sum over all objects that belong to the class, z to the size of the

object, divided by the size of the object's factorial.

That's what makes it an exponential generating function.

so, and just as With unlabeled classes. We have the fundamental identity that's

elementary, that you can express the generating function as the sum from N

bigger than 0, A N, the number of objects of size N, z to the N over N factorial.

And that's elementary because we just collect terms all the objects of size N

there's a sub n terms of size n and that's then an identity for the

generating function. And that means that, if we know the

generating function, a of z, and we want to know the number of objects of

size n, we just find the coefficient of z to the n, in a of z, and multiply by n

factorial. so that'll be our goal later on.

For right now, we're going to talk about how to build combinatorial classes and

how those constructions lead us to, equations that the generating function

must satisfy. With the symbolic method, just as for

unlabelled classes, we specify the class and at the same time characterize the

exponential generating function. So let's look at some basic labeled

classes. So one is called an urn.

That's just a set of labeled atoms order doesn't matter.

There's actually only one[COUGH] urn of each size, because the label doesn't

matter. It's just a set of atoms.

So that means the counting sequence, the number of urns of size n, is just one.

And what's the exponential generating function?

It's just sum of z to the n over n factorial times one, that's just e to the

z. That's a basic labelled class, the urns

the exponential generating function is e to the z.

permutations, that's another familiar labelled class.

A permutation is a sequence of labeled atoms.

And that's, here's the familiar, there's 24 permutations, of size four.

So, the counting sequence, the number of permutations of size n, is just n

factorial. What's the exponential generating

function. It's just one over one minus z.

The sum, n bigger than zero, n factorial Is the counting sequence times z to the n

over n factorial, 'cuz it's exponential generating function.

That's just the sum of z to the n, and that's one over one minus z.

That's a second basic example of a labelled class.

And a third one is a one that I introduced at the beginning.

It's a cycle. A cycle is a cyclic sequence of labelled

atoms. There's n minus one factorial cycles of

size n. So what's the exponential generating

function? It's n minus 1 factorial, z to the n over

n factorial. That's sum of z to the n over n or log of

1 over 1 minus z. So those are three basic label classes.

And they actually serve as the foundation of the commonotorial constructions that

we're going to consider. Now, the operations that we perform on on

label classes in order to create combinatorial constructions are based on

this operation the product operation. we had a product operation from unlabeled

classes, which was the Cartesian product, where we take one item from each class to

make a pair. Now this operation, called the star

product operation for labeled classes is the analogue to the cartesian product.

So, given two labled combinatory classes A and B, their star product, or labled

product is the set of ordered pairs of copies of objects, one from A, one from B

But they need to be relabeled in all consistent ways, and here's a very small

example. If we have a class that consists of a

single two cycle and another class that consists of a single three cycle and we

take the star product, we get a class that consists of ten pairs of objects.

We have the two cycle and the three cycle but we need to relabel them in all

consistent ways. We want to use the labels one through

five and we have to make sure in the three cycle that we maintain the

orientation. One to two to three.

Smallest to middle to largest. So for example on the left he shows all

the ways to assign one to the two-cycle. It can be with two, three or four and

then what's left over gets assigned to the three-cycle but in the order;

smallest, middle, largest, as we go clockwise around the cycle.

And then next is the two cycles with 2, without 1, there's 3 of those, with 3, 4,

and 5. And again, the ones that left over, the

labels that get left over, get assigned to the three cycle in the order smallest,

middle, largest as we go around clockwise.

And then there's three, four and three, five and again just two possibilities and

then finally four, five with one, two, three.

So that's the star product example of the star product for simple, labelled

classes. As you can see, the possibility

multiplies but this as, as, as you'll see is a perfect analog to Cartesian product

that let's us build up labelled combinatorial classes of remarkable

richness and complexity. for example, again you use a familiar

example. You can create permeation just by taking

Star products of Atom. So a single, permeation of size 1 is only

1, its just a Atom labeled 1. If you take the star product of 2 Atoms,

all you can do is label the first one 1, in which case the second one has to be

labeled 2. Or we can label the first one 2, in which

case the second has to be labeled 1. That's Z star Z, that's the permutations

of two elements. For each one of those, if you take the

star product again with another Z. then there's three possibilities, that

essentially labeling the first item either one two or three and then,

labeling the next two items, uh,[COUGH] has to be a sequence.

So, I, in all consistent ways just put the next two, the labels that are left

order, over, in the order. so that's the first three, and then the

second three is what you get in the star product of one and two one.

It's again, first one can be labeled one, two, three, and the others are labeled in

reverse order. And then for example the second

permutation in that list, two, one three, if we star product that with another z

then we get one, two, three, four, and then the remaining labels go in the

order, middle, smallest, largest. And then we get four possibilities.

For each one we get four possibilities. So that's a way to specify the set of

permutations using the star product operation.

and just as with the unlabeled classes we can write a squared for a star a, a cubed

for a star a star a, and so forth. and that's the simple example of a

combinatorial construction. We say that the permutations of length n

are z to the nth And we're going to next look at many other examples of

combinatorial constructions. But that's the basic operations for

constructing labeled 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