0:04

So now I want to finish up this lecture by giving an indication of how these kinds

Â of problems can be solved with analytic combinatorics in the symbolic method.

Â Essentially, those derivations, in a sense,

Â were a little bit the hard way, and there's an easier way.

Â Now we'll develop this fully in Part Two, but

Â it's worthwhile to take a look at a typical derivation using analytic

Â combinatorics because it's actually not that much more difficult.

Â And actually, the idea is to use bivariate generating functions.

Â That's really the way to analyze combinatorial parameters.

Â 0:45

So the idea is, for a combinatorial class, we have not just the size function, but

Â we also have an associated parameter that has a cost.

Â And we want to analyze the cost associated with the size.

Â We're looking for the average number of cycles in all permutations of size n,

Â and so forth.

Â So the way that we do that, say for unlabeled objects, is to just

Â take another variable, u, and to find the bivariate generating function,

Â z and u, where z is for size and u is for cost.

Â So for every object, we take z to the size of that object and

Â u to the cost of that object.

Â So that's what we work with for labeled classes.

Â We divide by the size factorial, but it's the same idea.

Â So that's the form that we're going to work with for permutations.

Â 1:40

Now, the idea is that those constructions that we gave are going to work

Â just as well to give us formulas that these bivariate generating functions have

Â to satisfy.

Â And not only that, the bivariate generating function really does carry

Â full information about the association between size and cost.

Â And again, it's pretty much as easy to compute as the CGF.

Â And we'll look at those computations next.

Â And not only that, using this approach with analytic combinatorics,

Â it's often the case that we can get full distribution or

Â the asymptotics of the full distribution by knowing and

Â generating a formula that the bivariate generating function has to satisfy.

Â So it's extension of the symbolic method beyond just counting to also

Â 2:39

So what are the basic calculations?

Â So we start with a bivariate generating function.

Â And this is exponential for labelled classes like permutations because that's

Â all the examples I've done so far today.

Â So if you want to go back to the way that maybe you're used to thinking

Â of things, and we had in our tables, actually,

Â the number of elements of size N with parameter value k,

Â then [COUGH] you have the fundamental identity

Â which just extends what we did for single variate generating functions.

Â If you're summing in all combinatorial objects,

Â you can gather them together by size and by cost.

Â And then the number with [COUGH] size N and cost k,

Â that's the coefficient of z to the N / N factorial u to the k

Â because every one of those objects will contribute one to the sum.

Â You gather them together, you ANk objects that have that sum.

Â And so that identity is implicit.

Â When we're trying to understand the combinatorics of it,

Â we work with the representation where we have a term in the sum for every object.

Â But when we want to do some counting, we use the elementary

Â identity to get us the results that we need.

Â So, for example, as I just said, the number of objects

Â of size N with value k, we can get from the bivariate generating function.

Â It's the coefficient of z to the N coefficient of u to the k multiplied by N

Â factorial for label.

Â 5:29

So just knowing that one

Â little really trivial calculation means that we can go ahead and

Â [COUGH] use our constructions to tell us about the bivariate generating function

Â and just do that one, differentiate with respect to u and evaluate at u = 1.

Â So this is the construction that we did earlier on, say,

Â for average number of cycles.

Â And this is the same slide as above so

Â I won't spend too much time talking about it.

Â So we apply our construction and

Â then simplify the sum to get down to the harmonic numbers.

Â 6:27

So now our same construction, which has

Â [COUGH] for every permutation,

Â we construct a bunch of other ones, and

Â p of those have the same number of cycles and one of them has one more cycle.

Â So that's what this equation says, those permutations of size p + 1.

Â One of them has one more cycle, so that's u to the cycles of p + 1,

Â and p of them have the same number of cycles, so that's u to the cycles of p.

Â So rearranging the terms and the sum according to this construction

Â implies that identity on the bivariate generating function.

Â And that one is not so

Â difficult to [COUGH] simplify.

Â So z to the p + 1 / (p + 1) factorial,

Â that means we should differentiate with respect to z.

Â And if we do that, then we get two simple sums that we can easily simplify.

Â The first one is just uB(z,u) and

Â the second one is like the derivative with an extra factor of z.

Â And you could check that.

Â That's a very simple calculation.

Â Now we can solve for derivative of u with respect to z.

Â 7:58

And we have B sub z (z,u) = u / 1- z B(z,u).

Â Now that's a differential equation in z that we can just solve,

Â and it's 1 / (1- z) to the u.

Â And it's a little shocking at first that there should

Â be such a simple solution, but once you think of u as a constant and

Â just work with the z, it's not so amazing a calculation.

Â And that's an explicit formula for B bivariate generating function.

Â And what do we want from that formula?

Â What we want is the average value of our parameter.

Â How do we get the average value of that parameter?

Â For any bivariate generating function,

Â all we do is differentiate with respect to u and evaluate at u = 1.

Â 8:49

Differentiate that with respect to u,

Â evaluate at u = 1, you get 1 / 1- z log 1 / 1- z.

Â That and the coefficient of z to the N in that is your average,

Â which is a harmonic number.

Â So the same kind of construction leads us to our result.

Â But what really makes bivariate generating functions the method

Â of choice is that we can actually get rid of this construction stuff and

Â really use the symbolic method.

Â And again, we'll talk about many examples of this later on, but

Â I want to show it for this one.

Â So the idea is to just carry the cost along with the combinatorial

Â constructions, and the transfer theorems and

Â everything else follow right through for

Â bivariate [COUGH] without much difficulty at all.

Â So the symbolic method will take us right to where we need to get.

Â So this says, a permutation is a set of cycles of Z,

Â and the variable u marks the number of cycles, and that's it.

Â So that immediately leads through transfer

Â theorem which is the same cycle as log of

Â 1 / 1- z and set as e to the power, and

Â immediately leads to e to the u log of 1 / 1- z.

Â So a simple combinatorial construction immediate transfer to BGF equation.

Â And there we are, no sums at all.

Â And what do we want?

Â We want to differentiate with respect to u, evaluate at u = 1.

Â And in this form, it's the same function that's 1 / 1- z to the u,

Â just written in the exp log form.

Â It's obvious that the derivative with respect to u

Â is going to bring out a factor of log 1- z.

Â And then leave this term, evaluate at u = 1, just 1 / 1- z.

Â So immediate from the transfer theorem to there, and then immediate

Â derivative evaluated at u = 1, which immediately gives our harmonic numbers.

Â So derivations of this simplicity replacing the ones we've been doing

Â is really persuasive evidence or persuasive bottom line that BGFs and

Â the symbolic method are the method of choice in analyzing parameters.

Â We're going to see many examples of that in Part Two.

Â 11:57

Well, it's a set of cycles that are not of size r plus cycles that are size r

Â marked with the cost variable u, and that's it.

Â And so by transfer theorem,

Â that immediately gives log of 1- z with the 1 for

Â r subtracted off, and then add it back on, marked with u.

Â So immediate from the transfer theorem to that BGF equation.

Â And then what's the value we're interested in?

Â We want to differentiate with respect to u, evaluate at u = 1.

Â And that is immediate,

Â differentiate with respect to u brings up to the z to the r over r,

Â evaluate at u = 1 just makes it e to the log of 1 / 1- z,

Â and that's the generating function for the average number of cycles.

Â And what's the coefficient of z to the N in that?

Â It's 1 / r as long as N is bigger or equal to r.

Â So working with the constructions in the way we did

Â earlier is at the level of detail that analytic combinatorics can free us from.

Â And again, we'll see many more examples of working

Â with parameters that allow us to use the symbolic method for

Â bivariate generating functions in this way.

Â [COUGH] So that'll be mostly in Part Two.

Â And just to quickly finish up without going into much detail, this parameter,

Â the number of permutations with size N with k cycles has got a long history and

Â lots of applications that we don't have the time to talk about in detail.

Â So it's called Stirling numbers of the first kind and

Â it's usually written nowadays in square brackets like that.

Â So for permutations of size 3, there's 2 of them that have 1 cycle,

Â 3 of them that have 2 cycles, and 1 of them that has 3 cycles.

Â And for 4 goes 6, 11, 6, and 1, and so forth.

Â So what we just did was show that [COUGH] if we just define the BGF for

Â Stirling numbers of the first kind,

Â we just showed that it's 1 / 1- z to the u.

Â And you can use that form to develop all kinds of interesting identities for

Â the Stirling number.

Â For example, the distribution for a given N,

Â the number of cycles of size N [COUGH] is

Â the coefficient of z to the N / N factorial, which,

Â if you use Taylor's theorem to expand this,

Â you get u times (u + 1), (u + N- 1), and so forth.

Â So if you take that polynomial in u, the coefficients of that

Â polynomial give you the Stirling numbers of the second kind.

Â And you can also come up with a way to compute them and get a recursive

Â formula like the basic formula for binomial coefficients and so forth.

Â We'll come back to some more details about this in Part Two.

Â I just wanted to point out that this kind of structure,

Â in more detail, has been studied a great deal.

Â In fact, here's a distribution with rescaling by N,

Â and actually one of the results in combinatorics

Â we studied tried to learn about limiting

Â distributions in situations like this.

Â And actually it can show that this distribution is normal in certain ranges.

Â 16:19

So that's the use of bivariate generating functions, and an introduction

Â of an easier way to deal with analysis of parameters in permutations.

Â So I just want to finish up by pointing out a couple

Â of exercises that people could do to test their understanding of the material that

Â we've talked about so far.

Â So the first one is this study, arrangements.

Â So an arrangement of N elements is a sequence formed by a subset of

Â the elements.

Â So that's a permutation of each element once and only once.

Â With arrangement, you could use some of them more often.

Â And so the problem is to study arrangements

Â 17:57

So, for next lecture, read the [COUGH] Chapter Seven in the text.

Â Again, it's encyclopedic so you might find yourself skipping through analysis of

Â certain parameters, but some of them have interesting applications.

Â I think it's always a good idea to run

Â some experiments to validate the mathematical results that we've developed.

Â And it's easy to generate random permutations, so why not do it to just

Â check that, say, the average number of cycles or the average number 1-cycles in

Â a random permutation agree with the results predicted by our analysis.

Â And even for distribution for that exercise we're doing the distribution of

Â cycle length takes more computer cycles to study cycles,

Â but it's worthwhile to run experiments to validate these things always.

Â And again, it is worthwhile to

Â