0:39

Recall that we're going to define generating functions for

the counting sequence and for the accumulating cost.

And then we're going to have a construction, and the construction will

give a generating function equation for the accumulating generating function.

And then we're going to either solve to get an explicit formula,

or find another way to extract coefficients to get the counting sequence.

And the cumulated cost and then we divide the cumulated cost by

the counting sequence in order to get the expected value.

And we did that for the leaves and binary trees last time.

And that's the general approach

that we typically use in analytical common torques to analyze parameters.

Now for permutations, there's a small trick.

There's also a small trick for strings, we'll see next time.

2:42

So this works because N factorial is both

the normalizing factor, and it's the counting sequence.

So really this is shorthand for N factorial times the coefficients of ZP and

BZ is the total cumulative cost.

N factorial is also the counting sequence.

So if we just extract the coefficient of Z to the N.

We get the average for permutations.

So that's what we're going to do, is we're going to work with the, an exponential

accumulated generating function, but then when it's time to extract coefficients.

We'll just extract coefficient at z to the n and

immediately get the average value of the parameter.

3:29

It takes quadratic time for randomly ordered permutations, but

it's the method of choice for some situations.

For example, when records are large,.

You can read about that in the algorithms book,

and it's a very simple algorithm that goes through from left to right.

The first thing it does is find the minimum element in the permutation,

exchanges that with the first.

Then it finds the minimum in what remains, and exchanges that with the second and

so forth.

So, first question is, how many times

there's a variable that keeps track of the current minimum in this code.

And the question is, how many times is that variable updated?

Assuming that all the keys are distinct.

So, in this example, we start out thinking that S is the minimum, O is less.

So we update it.

4:41

So, that's what we want to analyze first.

Now so, that's our question.

How many left to right minima are there in a random permutation?

Now, from a practical standpoint,

this question is maybe less important than some of the others we talk about.

Because this cost is not significant compared to the number of compares.

But still, it's a fundamental property of permutations that we want to study.

So a left to right minima, or we call an lrm, in a permutation.

It's a parameter, a permutation, and

it's an element that's smaller than any item to its left.

5:21

So if a permutation begins with one, like the ones on the top in

this example It's only got one left-right minimum the one.

If it begins with two.

It's got exactly two.

The two and the one.

If it begins with three.

It might have two, or it might have three and so forth.

Permutation in reverse order size N has N left-right minima.

Each new one is a minima.

And so, these tables in our standard form show for

each permutation the number of left-right minima off to the side.

Then the total cumulative cost is just summing those numbers,

or the [COUGH] for three elements, accumulated costs.

There's two that cost.

One and three that cost two, and one that costs three sets of total of 11.

Divide that by n factorial, the average number of left to right

minima in a random permutation of size three is 1.833.

And similarly, for size four, it's 2.083, and so forth.

How many left to right minima in a random permutation of size n.

So, that's our questions.

And again, as usually, it's very worth while to fully compute small values

both to get an appreciation for the intricacies of the problem.

And also to have precise values to check against when we complete the analysis.

So that's what this table is.

So what we're going to do is use a combinatorial construction to help

us derive directly a relationship

that the cumulative generating function has to satisfy.

And that's figuring out which construction to

use is the art of analytic combinatorics for these kinds of problems.

7:51

So now if you look at the original permutation.

In this case, has three left to right minima.

All the permutations that we got from the star product have the same

number of left to right minima,

with the exception of the first one has an extra one, which is the one at the end.

So that construction and that observation tells us if we

know the number of left to right minima in the original permutation.

We know the number of left to right minima in all the permutations that we

constructed.

And that's, there's p + 1 of them, and

every one of them has the same number of left to right minima as p did.

So those copies, and then there's one extra one.

The one that ends in one.

So that's the combinatorial construction for permutations.

And then we're going to use that to derive a formula that

the generating function, the cumulated generating function, has to satisfy.

P plus one lrm or plus one.

So to compute the average number of left right minima in a permutation.

We define the cumulated generating function, which is the sum for every

permutation of its number of left-right minima times the size or size factorial.

And again, if you group the permutations by their size,

that gives the cumulated cost.

The exponential generating function for

the cumulated cost, which we'd know at the end.

So now if we apply the construction.

Every permutation gives us p+1 permutations.

So in the number of left-right minima in those permutations is size of

people of one algorithm p+1 size of the permutations that we construct zero p+1.

So, applying that construction it immediately applies

that equation on the generating function.

And that's an easy equation to simplify.

So the first term, if size of p plus one lrm of p,

and that size of p plus one cancels with the size

of p plus one factorial below the z size p plus one.

So that gives us the first sum, lrm of p plus one over p factorial.

And then the second term, the plus one just throws out

a second term with z over p plus one or p plus one factorial.

So that's a simplification.

Now both of those we can evaluate.

The first one if you look up at the first equation is just z b of z.

12:42

So that's left to right minima.

Now a similar question in terms of parameters on permutations.

Suppose we want to know the number of cycles that are in

a permutation with size N.

And again, if we look at this table.

The number of cycles in each one of the permutation's is written to the left.

And we can go ahead and compute the accumulated costs.

And probably you already recognize that it's the same number.

So now we're going to look at why it's the same number.

So to analyze the average number of cycles in a random permutation

we'll use the same basic approach.

We'll look at a construction that constructs permutations.

Given one permutation construct of size n construct n plus one of size n plus one.

And use that construction to rearrange the terms of the sum and generating function

function to imply a relationship that that generating function has to hold.

So for cycles,

what we're going to do is we have a permutation that's a set of cycles.

We're going to insert, and it's a size n.

We're going to insert n plus one into every position in every cycle,

including the null cycle.

14:04

So first thing is, put seven in the null cycle.

So that creates a new cycle of size one, and

then put seven in every position in the one cycle.

There's only one place that makes it two cycle with two and seven in it, and

then in the two cycle.

There's two places to put it, 376 or 367.

And in the three cycle, there's three places to put it.

Either 4715, 4175, or 4517.

So, that permutation of size six.

We construct seven permutations of size seven.

14:45

And so now the question is,

how many cycles are there in all of these permutations?

And so, if the number of cycles in the original perm is cycles of p.

Then how many are there in all of these.

Well, they all have the same number of cycles.

Except the case where we added a new cycle by adding to the null cycle.

So, there's p plus one, copies the original perm, and

all of the same number of cycles.

And then, there's one extra for that extra singleton cycle.

15:31

So, instead of LRM, I wrote cycles but it's the very same derivation.

We apply the construction and use that to essentially reorder the terms in the sum.

We say the generator function also has to equal that expression.

Then it simplifies in exactly the same way to get down to the harmonic numbers.

Average number of cycles in a random permutation of size N is A sub N.

Now, when we have the same generating function again,

often in combinatorics, when we see that.

What we like to do is find a correspondence,

a one to one correspondence between the number of LRM and the number of cycles.

So it's a reasonable question, is there a one to one correspondence.

This is a famous one, and the answer is yes.

So what you could do, if you have a set of cycles.

You can build a permutation corresponding to that set of cycles.

A unique permutation corresponding to that set of cycles.

By looking at the smallest element in each cycle, call that the leader of the cycle.

So the first one, the four is the leader.

The second one, the one is the leader.

The single cycle there's only one.

The third one, the 14 is the leader.

And the last one, the two is the leader.

So we identify the leader of each cycle.

And then what we'll do is write down the cycles in decreasing order of the leader.

So we pick the largest leader and then write down its cycle,

just by following the cycle.

So in this case, the largest one is 14.

That's where we write 14, 60.

The next largest leader is just the five.

The next one is that first one, where the leader is four.

So we write down four, ten, six, 15.

And then the big one at the end, we write down two, 12, eight, three, 11, 13.

And then the one containing the one is one, seven, nine.

Now we don't write down, we didn't demark

the cycles in any way, but that's a permutation.

And so, I said it was unique and that means we can use a corresponding

process to get the set of cycles corresponding to any permutation.

What’s the set of cycles corresponding to this permutation?

So we’re given the permutation.

What we do is, identify the left to right minima.

Those are the leaders.

Remember we pick the leader as the smallest in the cycle, and

then we wrote them down in decreasing order of the leaders.

So between each leader, say between four and two.

Everybody on the same cycle as four is bigger.

And so, as soon as we get to somebody that's smaller than four,

that's the leader of the next cycle.

So that's how we break up the permutation into cycles and that immediately

shows that the number of left to right minima is equal to the number of cycles.

because this correspondence is one to one, and works for any permutations.

So that's a famous correspondence between left to right minima in cycles.

That so, now we can write down the cycles just by finding the lrm,

and then simply writing the cycles out as before.