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.

Â