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.