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