0:03

Next we're going to talk about another important class of

combinatorial classes that has to do with labelled objects.

And I'll explain the distinction between labelled and the unlabeled ones that

we talked about and then look at some interesting problems.

So labelled combinatorial classes, the objects have N atoms, but

we consider the atoms to be all different.

And to just make that clear, we label them,

consider them to always be labelled with the integers one through N.

0:48

But when they're labelled, [COUGH] there's different ways

to label them that make different objects.

For example, that's two different ways to label that square.

[COUGH] So in the one on the left, 1 is connected to 2 and

4, the one on the right, 1 is connected to 3 and 4, they're different.

And this one,

it's not always clear how many different ways there are to label things.

In the one on the right then there's three different ways to label that,

either 1, 2, or 3, there's actually four ways.

1, 2, 3, or 4 are going to be the ones that are connected to everybody else.

So there's a big difference in studying the number of different

objects because the labels provide so many more possibilities.

In fact, when we're working with labeled objects,

we use exponential generating functions for that reason.

And that'll become clear as we move along.

2:38

The next one is a familiar one, it's permutations.

A permutation is a sequence of labelled atoms.

Sequence means the order is significant.

Atoms are labelled so

every possible ordering of the atoms is going to give a different object.

So there's 2 different objects of size 2, either 1, 2 or 2, 1,

6 different objects of size 3, 24 different objects of size 4, and so forth.

3:42

Here's another one, a cycle.

A cycle is the cyclic sequence of labelled atoms.

So everything is connected in a circle, but

now there's fewer of each type.

And in fact, actually, if you study it for a minute,

if you just fix on the largest to the smallest element,

then you can see that the others are permutation.

So actually the counting sequence is (N- 1) factorial.

4:11

So what's the exponential generating function for cycles?

Well, it's the sum of (N- 1) factorial z to the N / N factorial,

which everything cancels but an N, so it's natural log of 1 / 1- z.

So that's another basic combinatorial class.

Now it's very characteristic of analytic combinatorics to start with

extremely simple derivations in classes like this, but then combine

them in interesting ways to provide answers to analytic problems of interest.

4:50

So what about the analog to the Cartesian product operation?

Well, it's much more complicated for labelled classes.

When we take the product of two classes, so we're going to say,

this first example 1, we call it the star product.

1 star product of 1, 2, 3, what we're going to get is

object of size 4, but they have to be numbered from 1 to 4.

And what the combinatorics requires is that we do that

numbering 1 to 4 but we do it in all consistent ways.

So in this case, the second argument is a sequence that's in increasing order.

So when we renumber,

we have to put that in increasing order on each one of the possibilities.

So we can assign 1, 2, 3, and 4 to the first one, and then the reaming labels,

we assign to the remaining 3 atoms, but they have to be in increasing order.

And here's a more complicated example,

where we take the star product of a two-cycle and a three-cycle.

Again, when we do that, we get 5.

We have objects consist of five atoms that have this structure,

a set of a two-cycle and a three-cycle.

The atoms have to all be numbered with 1 through 5, and

we have to do it in all possible ways.

So in this case, you can choose any label.

So there's only way to label the two-cycle.

And then you can choose 5, choose 2, or 10 different ways to label the two- cycle.

So, the first column is,

with the top one being 1, you can have 2, 3, 4, 5 for the bottom one.

Second column's top one being 2, 3 and 4.

Then, after you've labelled the two-cycle then

you take the remaining labels and assign them to the three-cycle,

but you have to be consistent and maintain the order.

So, for example, with 3, 4, in this case with 3, 4's, the labelled two-cycle,

the remaining labels are 1, 2, and 5, and they have to go in that order.

So that's the star product operation relabeled in all consistent ways.

And when we get to applications, we'll see why that's

not just intuitive, that's fundamental to working with labelled objects.

So with labelled objects, since you can tell the difference in the ordering,

we have more basic constructions and

it's a much richer set of operations that we're going to work with.

And actually, the ones that I'm giving work for labelled and

unlabeled are only the beginning.

Research is ongoing and people have developed many,

many more constructions than I'm going to present here.

7:53

So [COUGH] plus is the same, you take copies of objects from A and

B, but you relabel in all consistent ways.

Star product is where you take ordered pairs of copies.

Sequence is similar to what we did for a unlabeled.

It's A plus A star A plus A star star A, and so on and so forth.

But you could have sets of objects, like we did for urns.

And you can have objects arranged in a cyclic sequence for example.

8:29

So those are the constructions we can use.

A richer set of constructions leads to a richer set of objects we can talk about.

Again, what's important is that we have a transfer theorem.

If we have combinatorial classes, and we know their EGFs.

Then whatever operations we pick from that list.

We're going to know the EGF of the result of that operation.

As before, if we do disjoint union we have the sum.

If we do the labeled star product.

We have the product of the generating functions.

9:27

cycle is a z k over k, and cycles of any length.

Cycles of size k is that any length is log of one over one minus a z.

So if we know the generating function for combinatorial class.

When we perform one of these operations we know the generating function for

the result, and that's extremely powerful transfer theorem.

It's the basis for the symbolic method.

So let's just look at the basic constructions of the basic objects using

these operations.

So urns, urn is a set of atoms.

And that immediately translates to e to the z form the transfer theorem for sets.

11:45

So A plus again is separate into B disjoint sets, and

that immediately gives the result.

First star, it's a conclusion of the type that we've seen before,

but let's take a look.

So, to do all different re-labelings.

So, we take one alpha from A and beta from B, and to do all different re-labelings.

It's alpha plus beta, choose alpha.

Just like with the example I did with the cycles.

And then.

12:21

So that's a number of ways you can relabel.

And then the size of an object composed of an alpha and

a beta is e to the alpha + beta.

And again, the factorials are from alpha + beta factorial.

And then if you take that complicated sum, the alpha plus beta

factorials cancel, and you can separate out CV alpha or alpha factorials.

Either beta over beta factorial to get that it's a product.

Again, that's a complicated convolution, but

this is the only time we have to do it.

12:56

And for the other operations, I have a slide that's

got lots of dense math on it, but it's pretty simple.

So as we saw before, A of z to the k is the number of k sequences.

It's the exponential generating function for the number of k sequences of size N.

So that's just as we saw several times before and

if you add those all up for a sequence of any length, you get 1 over 1 minus z.

But if you have all the K sequences of size n.

Then you're going to have each k cycle of size n

appear k times there in each cyclic orientation.

So that means that A of z over, to the k over k is the EGF for

k cycles, for cycles of k objects and then summing all

those up gives the result for cycles of any length.

Similarly of you have all k sequences of size N

you're going to have all sets appear k factorial times.

So that means that A to the Z to the k over k factorial is the exponential

generating function for the number of k sets of size N.

Summing all those up give the result that for any set.

It's e to the A(z).

So these are worthy of study.

But they're very straightforward and immediate from the definitions.

And the basic ideas of generating function counting.

So let's look at a much more interesting example.

So, the idea is that we have these operations.

We can combine them in various interesting ways.

And actually, as we'll see in part two.

There's, every way of combining these basic operations leads to

a combinatorial class that people are studying in detail.

But there's many more operations we can throw in as well.

So let's look at this, this is a famous one.

How many different sets of cycles are there of labeled atoms?

For example, for

three atoms you could have a cycle of size three.

There's two different ways to label that, or you could have one cycle of

size one and another cycle of size two.

And there's three possibilities for labeling that, or

you could have three cycles of size one.

So it's a total of six sets of cycles of labeled atoms.

15:37

And if you work it out for

four on the right is all the possibilities of sets of cycles of four atoms.

You could have what'd be four singleton cycles, or

you can have one cycle of size four.

And there's six different ways to label that one, or

you can have something in between.

All the possibilities are laid out here.

You might recognize the numbers.

And yes, there's N factorial sets of cycles of N labeled atoms.

And what we'll look at next is how we learn that from analytic combinatorics.

And it's not just instructive.

It forms the basis for

us to solve problems that we couldn't otherwise solve, as you'll see.

So let's use our regular methodology.

We have to articulate what our class is.

So it's P*, is the class of all sets of cycles of atoms.

Number of atoms is the size.

The EGF, as usual, brings together its coefficient is z over N factorial,

is the number of sets of cycles of atoms.

16:49

The atoms are just labeled atoms, for labeled classes it's always the same.

[COUGH] What's our construction?

A, nothing more than saying a set of cycles of

atoms is a set of cycles of atoms.

That's what the math says.

And it immediately translates from the transfer theorems to

cycle of z translates to natural log of 1/1-z.

Set of something is e to that power and

that's just 1/1-z.

Therefore, the counting sequence of n factorial is n factorial.

That's the same as for permutations and again, that's a very quick result,

it just comes from the combinatorial description.

A set of cycles that we could get the generating function for

sets of cycles immediately from the transfer theorem.

18:32

That's a cycle.

We can depict that thing just like this,

just when you go from 4 to 10 to 6 to 15 back to 4.

And if you've already done an item, ignore it, otherwise do this process,

you can convert any permutation into a set of cycles.

And it's a worthwhile exercise to figure out how to

reconstruct the permutation from a set of cycles, but that's a well known bijection.

So that brings us to our first

20:21

Now, just as an amusing aside,

this problem has been posed in the centuries since in many different ways.

That’s the classical opera way.

So some people say well a professor returns exams to students by passing them

out at random, what's the probability that nobody gets their own exam.

So a lot of people use that where you're posing the problem in

combinatorics classes.

Or a more fun way to do it is the drunken sailors.

So you have a group of sailors that are a bit inebriated and

when they get back home, they wind up sleeping in a random cabin.

So what is the probability that nobody winds up in their own cabin?

21:08

Or maybe more relevant to college students is, got n students who

live in a single room and they get also in a state of inebriation.

What's the probability that nobody ends up in their own room?

That's all the same problem.

And to solve that problem, what we want to do it count derangements.

So derangements are permutations with no singleton cycles.

So this is our table of sets of cycles, which are equivalent

to permutations with the ones that have singleton cycles grayed out.

So there's nine permutations of size four that have no singleton cycles.

Probability that nobody winds up with their own hats is is only 4 of 9 over 24.

And so, this maybe is not a familiar sequence.

So let's see how to analyze that with the symbolic method.

24:30

So that's the result is that it's asymptotic to one over e and

let's just look at each of the elements of that.

So first of all, we're lookin and since we want a probability,

it's convenient that we're using exponential generating functions.

And our probability denominator is N factorial,

so we're taking advantage of that [COUGH] coincidence.

It's not really a coincidence, but in this case it works out.

So to get the probability we just look at the coefficient of z to the N in

the generating function.

Not N factorial times z to the N because it's going to divide right now.

So [COUGH] that's a D to the N over N factorial and what's that coefficient?

Well, it's a convolution e to the minus z times one minus z.

You just do the convolution, the coefficient of Z to the N and

that is the sum of k from zero to n and minus one to the k over k factorial.

And that's a straight convolution.

Then that's a sum that we looked at as one of our examples for

bounding the tail in the asymptotics lecture.

To show that's asymptotic to one over e and that's very close to one over e.

26:40

And so there's the idea of generalized derangements.

So if you've had a random hat,

you can always get your own hat back by following the cycle.

So student four wound up with ten's hat.

She can go to ten and ten's got six's hat.

The she can go to six, six has 15's hat.

The she'd go to 15 and 15 there's her hat.

So following the cycle will get your hat back.

So then now we have the more general problem,

what's the probability that all cycles are of length bigger than m?

That everybody's would have to follow at least M

27:46

D sub N is a class of all generalized derangements.

No cycles in a linked list that are equal to N.

Everything else is the same.

So the construction is, it's a set of cycles that are bigger than M [INAUDIBLE].

That translates directly to generating functions,

you just start at Z to the M + 1.

So it's the same series now starting at Z to the M + 1.

Or that's log of 1 over 1 minus z minus z squared over 2

all the way up to z to the M over M.

And simplifying that, we have e to the minus z minus z squared over

2 minus z cubed over 3, so forth up to z big M over m over 1 minus z.

So that's the generating function that we get immediately from the symbolic method.

28:37

And quite simply without the symbolic method,

you might have some trouble getting to this generating function on your own.

So that's certainly a lot of these

things is possible to do because what's behind the symbolic method is so simple.

But the symbolic method really makes it so that a child can do it.

So that's a generating function equation.

Now to find the answer to this problem,

we need to extract coefficients from this equation.

Now that one, not so clear.

That would be an M way convolution and go ahead and

try to extract coefficients from that one.

So that's going to motivate, how can we find the coefficient,

how can we estimate the coefficient of z to the N in that complicated function?

That's going to motivate the second part of analytic combinatorics,

the analytic transfer theorems.

But that's a basic introduction to symbolic method for labelled objects.