0:41

so if you have that approximation of g, then taking e to that power, which the

Â set's supposed to do. gives you a good approximation of F.

Â And then you can extract coefficients from the standard scale using F.

Â And again, there's a lot of detail to proving this fact, involving the

Â singularity analysis process. but once it's proven then we can apply it

Â easily in lots of applications. and also there's a corollary that

Â immediately gives the average number of components in a random object where it's

Â alpha log N where alpha is the mul, coefficient of the, of the log in the

Â approximation. so that's again a transfer theorem from

Â the last lecture. And now we're going to look at

Â applications. and the first one is and again we'll just

Â be focusing on the coefficient asymptotics.

Â first application is all about cycles and permutations and again, just to refresh

Â memories for people who didn't see the last lecture, well, take a look at this

Â one. and we also, not just interested maybe in

Â permutations, but how many cycles are there on an average.

Â [INAUDIBLE] In a random permutation. and we've looked at this problem, we've

Â looked at this problem as an example all the way back through part one of analytic

Â [UNKNOWN]. but now we're going to show how this

Â problem and variants of this problem and problems like it are immediately handled

Â with a general schema. so our construction is a permutation is a

Â set of cycles. so that immediately translates to e log

Â of 1 minus e for the cycles, e to that power for the sets, x blog.

Â so that form of the generating function says we're going to use uh,exp, the

Â exp-log theorem. so now its what we want to do is

Â calculate the alpha row and beta but those are immediate

Â 2:52

Because in this case it's not approximation.

Â the thing that's raised to the, e is raised to that power is log of 1 over 1

Â minus z. So that's alpha equals 1.

Â Beta equals zero. There's nothing added on.

Â And row equals 1. So we just plug in alpha equals 1.

Â Gamma of 1 is 1. Beta equals 0 so that's a 1.

Â rho equals 1. So it's 1 to the N.

Â and all that's left is 1, from exp-log. So the coefficient of z to the N of P of

Â z is asymptotic to 1. And it's exponential, so number of

Â permutations as sub type n factorial. that doesn't seem like much of of much

Â interest. But remember the correlary says the

Â expected number of components. So that's the expected number of cycles.

Â Which does maybe require some [INAUDIBLE].

Â Some calculation it's alpha log in. Alpha's one so that's immediate through

Â singularity analysis prove that not just the number of permutations.

Â But also the average number of components comes immediately log in.

Â and again for The basic problem like this we have lots

Â of ways to proceed to improve the log in result.

Â Our point is that for variance of this structure or for other similar structures

Â we can use precisely the same process to get an answer where direct calculations

Â might be extremely complicated. Were prohibitive.

Â So like, examples. So we looked at derangements.

Â So we can look at derangements. Or we can look at a problem like, how

Â many cycles are there in a random derangement.

Â might be hard to think about how to even approach a problem like that.

Â but it's immediate from the X blog schema.

Â And precisely the same process works for more general settings.

Â Like maybe we want to know about cycles and derangements.

Â We talked about derangements, which are the set of all permutations having no

Â singleton cycle so we take out the singleton cycles.

Â So that's the construction. It's a set of cycles none of which, all

Â of which are lengths greater than one, greater than zero and so, all we do is

Â subtract off, one from log of one minus z to take out the singleton cycles.

Â D is, equals x log, [INAUDIBLE], or one minus z minus one.

Â that's x blog. The only difference is that, now that

Â beta is minus one. So it's the x blog form.

Â it's just that beta is minus one. So,

Â When we now, apply the theorem, we get the same answer.

Â except that, 'cuz of the e to the beta, we get e to the minus 1.

Â and that's a familiar result. the number of [INAUDIBLE] have to

Â multiply by n factorial. It's n factorial, over e.

Â and when you looked, we looked at this as an early example in part 1 of the course.

Â and that 1 over e started out as a finite sum and we had to show that the tail's

Â negligable, and so forth. this higher level way of looking at the

Â same problem really gives insight in where this form of the solution comes

Â from. it's all about the minus one.

Â And we subtracted off the minus one. That translated right through the

Â theorem, down to the exponent of e. and not only that, we have the

Â correlative theorem which tells us, average number of cycles in a random

Â derangement. But still log in, doesn't involve data,

Â data so the average number of cycles in a random derangement, is proportional to

Â the log in still. And this generalizes to include any

Â restrictions on the cycle links. So you could pick t different integers

Â and say I want to study the class of all permutations having no cycles of length

Â w1, w2, down through wt. the uh,construction is, just sets the

Â cycles with that restriction on the cycle length, immediately translates to a

Â generating function equation where we subtract off the term corresponding to

Â each one of those cycle lengths from log of one over one minus z.

Â but when applying the explog theorem all that does is when we approximate that

Â function near the singularity, which is rho equals 1.

Â Those Z to the Ws become 1. it all comes to the beta.

Â so applying the theorem then we're just going to get e to the minus theta.

Â and then it's just e to that constant and whatever those constraints are, you can

Â compute the constant, and you can know that the number of generalized

Â derangements of that form are n factorial over e to that constant, very easy to

Â compute. pick 2, 3, 5, 9, and 11, and you can

Â compute the number and know that average number of derangements that don't have

Â cycles of length 2, 3, 5, 11. You might be challenged to try to derive

Â a result like that using elementary techniques.

Â 9:07

let's look at a a much more complicated problem to to deal with.

Â this is called the two regular graphs. it's actually not at all more complicated

Â through analytic combinatorics. so these are undirected graphs where all

Â the nodes are degree two. so every node of degree two essentially

Â means it has to be a little circle. There's only one to regular graph in size

Â three it's a little triangle and there's only one way to label that one because

Â it's not any different. So that's like, down there at the right,

Â is the representation of the graph as a set of edges.

Â If we have an edge from 1 to 2, and edge from 1 to 3, an edge from 2 to 3, then

Â all the nodes have degree two and the, that's the only possibility.

Â for four-node graphs to keep all nodes of degree two.

Â Sines gotta be a little circle. But now there's a bunch of different ways

Â to label it. and get different graphs.

Â so in this case, there's three different edge sets.

Â so you fix one of the nodes and do the premutations but then after removing the

Â flips This so, either order counts the same in

Â this type of graph, because the set of edges won't see the difference, how you

Â draw it. and so for five, it turns out that

Â there's is twelve. again fixed one is twenty four

Â permutations, and each one appears twice in both it's orientations.

Â the, for 6 now you could have, the 6 node graph and again, 60 ways to label that.

Â Or you could have 2 3 node and that would work fine.

Â So there's actually 70 different, 6 node graphs.

Â That's with, one two three four five six edges.

Â that every node has degree to. There's 70 of them.

Â so that's and for seven nodes there's 465.

Â and as we get more we can have different combinations of the little ones.

Â So it's a set of gr, subgraphs and sub components of this type and then the n

Â minus one factorial, or k minus one factorial over two ways label it if it's

Â given. So, you can work with elementary methods

Â to try and count these, but with analytic comminatorits, it's actually quite easy.

Â you also might want to know the number of components in in a random two regular

Â graph. so this one there's one component for 60

Â of them and there's two components for ten of them, so that's an average of

Â 1.143. And for this it's 1.226.

Â so, maybe in some application in chemistry or some physical process, you

Â might have a situation where you need, you have a random structure of this type,

Â and you want to know the number of components.

Â That's the kind of problem that we're getting at with this kind of analysis.

Â 12:40

So what is a two regular graph? It's a set of undirected cycles of three

Â or more nodes. That's all.

Â that's actually a fairly compact specification of what it is.

Â That immediately translates the generating function equation.

Â Its half undirected cycle means you take half, that's the same as when I the, each

Â graph appears twice. and then again we have to subtract off

Â the the small ones z over 2, and z squared over 4.

Â That's a classic to regular graphs. so now that looks a bit complicated at

Â first, until you realize that it's x blog form.

Â So exp log form, and all it says is what's raised, e to the power, what's in

Â that power is some constant times log of 1 over minus z times some constant plus

Â some other constant. asymptotic to that near the singularity

Â closest to the origin. Singularity closest to the origin is 1

Â near that. we have beta equals three-quarters.

Â we have alpha equals one-half, that's the coefficient of the log.

Â we have rho equals 1. Immediately now, we can apply the

Â theorem. Beta's three-quarters, so we have either

Â the three-quarters. Alpha equals one-half, so we have gamma

Â of one-half. and and that's it.

Â 14:16

So immediately the exp-log theorem translates from the generating function

Â equation to the coefficient asymptotics. You need the minus three quarters over

Â square root of pi n. and so if you want to get the number of

Â two regular graphs, you multiply that by n factorial.

Â the very general theorem when we're using the set construction the x log theorem to

Â get coefficient asymptotics. And this type of asymptotics would be

Â quite difficult to get using normal techniques.

Â Now again, underlying this theorem is singularity analysis, as it, so there's

Â quite a bit of mechanics under there. But when it comes to applying it's no

Â problem. And again the component corollary applies

Â here. now we have alpha equals a half, so

Â average number of components in a random two-regular graph of size N is half log

Â N. A very easy to get results of this type

Â using the x log schema. So that's our second example of a widely

Â applicable, schema that's based on a singularity analysis.

Â