0:00

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.

Â 4:35

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.

Â