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.

Â