0:04

Next, we'll look at two more examples of parameters in permutations.

Â Again, just to gain some comfort with the b asic method and

Â also to get more familiarity with the properties of permutation.

Â And there are many, many other examples in the book.

Â We were picking four parameters of permutations and

Â there's another Five or six or more in the book.

Â So say you want to know how many 1-cycles are there in

Â a random permutation of size N.

Â So for two,

Â the average number 1-cycles, there it's just one

Â because the Permutation has 2 1 cycles.

Â Has 2 and the one that's a 2 cycle has 0.

Â So the accumulated cost is 2.

Â And we divide it by 2 we get 1.

Â For 3 we have either 3 1 cycles which is 3 to the accumulated cost.

Â We have three of them that have 1 1 cycles so that adds another 3 to the cost.

Â So again the total is accumulated cost is six and

Â then thereâ€™s the six of them so the average is one.

Â And you might start to see a pattern in and sure enough for

Â permutation of size for the total cumulative cost and you can count to here.

Â There's 24 1 cycles in all these permutations and there's 24 permutations,

Â so the average is 1.

Â So we're going to expect our result to show that the number of 1 cycles averages,

Â expected number of 1 cycles in a random permutation of size n is 1.

Â 1:51

To show that, we're going to use precisely the same construction that we

Â used for counting cycles.

Â So again, we put p + 1 at every position in the cycle.

Â The difference in the analysis is, if the original

Â perm has cyc1 of p1 cycles How many are there in the set of constructed perms?

Â Well, you have the same equation to start out with.

Â That is that whatever number 1-cycles there

Â are in the original there's people as 1 times that in all of these.

Â But then we have to adjust to add the new one cycle,

Â when we added our new element to make it a one cycle.

Â And then we have to subtract off for

Â every one cycle that was there in this case, the two.

Â We knocked it out by making it into a two cycle in one of the perms.

Â So we have to subtract off cyc1(p).

Â So that gives us a slightly different formula.

Â The number of one cycles in the set now is p

Â times cyc1(p)+1 instead of p+1 times cyc1(p).

Â So just that plus one Is the difference between this

Â 3:03

equation and the one that we did for left to right minimum in for cycles.

Â So let's look at what happens to the analysis when we do that.

Â So, CGF.

Â And then we apply the construction.

Â And again, the only difference is there was people before, and now it's p.

Â 3:54

And now the second one is just the for.

Â The permutation, that's one over one minus z, in the first one, the p cancels

Â out, and so that is just the prime of z, so if

Â 4:13

you take the derivative of b of z, if you look in the upper left,

Â the first formula, The p cancels out with

Â the p factorial in the denominator.

Â And then we are just left with an extra factor of z.

Â So it's b prime of z.

Â And then plus 1 over 1 minus z.

Â And that's our answer.

Â So now we have a differential equation b prime z equals one over one z minus

Â squared.

Â and that's easy to solve it's just one over one minus c and coefficient z is one.

Â So average number one cycle in a random permutation is one So

Â 5:21

So, for example in our Students and

Â Rooms Problem everyone goes back to a random room,

Â what's the average number of people who wind up in their own room?

Â Well, what we just proved is that it's one.

Â 5:38

Now, just to test yourself or your understanding of this method

Â it's worthwhile maybe to take the time to try to figure out the number of,

Â expected number of two cycles in a random permutation of size N, or then generalize

Â that to the expected number of R cycles in a random permutation of size N.

Â Now the answers are 1 over 2, and 1 over r.

Â In you can by solving this problem you can see

Â get a little practice with the manipulating this kind of equations.

Â As our last example of studying parameters and permutation we look at inversion.

Â An inversion in a permutation is a pair that is out of order,

Â that's a little bit imprecise.

Â A better way to look at it is to say, it is the sum for

Â each entry, we sum up the number of elements that are larger and to the left.

Â 6:40

So for example in the top right corner one two four three,

Â the only pair that is out of order is three and four.

Â So three has one larger element.

Â That's left before.

Â All the rest of have zero or larger elements to the left.

Â The one below that, 2143 has two inversions, 1 and 2, and 3 and 4,

Â are out of order.

Â 1 has one larger Drome and to its left three has one larger elements to its left.

Â The one below that 3 1 4 2 that one has three inversions because 1 has one larger

Â element to its left the 3 and 2 has two larger elements to its left the 4 and 3.

Â And again for every one of these permutations we have written down

Â off to the side the number of inversions.

Â If you add all those numbers up you get the cummulated cost.

Â For three, the cummulated cost is nine so

Â the average number of inversions is one and a half.

Â For four, the total cummulated cost is 72.

Â So the average, so

Â the accumulation across the field is the expected number of inversions is three.

Â 7:51

So that's the quantity we want to study, the number of inversions.

Â An application of this is to analyze another elementary sorting algorithm

Â called insertion sort and that's also the method of choice in some situations and

Â you can read about it in algorithms.

Â 8:20

what insertion sort does is goes through the array.

Â For every position I,

Â it's job is to keep all of the elements before I in sort of Order.

Â And the way that it does that is when it gets a new element,

Â it exchanges it with all the larger elements to its left.

Â 8:40

So in this case, when i equals 10 and it's pointing at the m,

Â it knows that everything to its left is already sorted.

Â But looking at the current element,

Â its element to its left is larger so we exchange.

Â We keep exchanging as long as the element to its left is larger, so M is still

Â always larger and N is larger and when it gets to a point where they almost

Â just left to smaller then it's inserted into its proper place in the array.

Â 9:12

So it's known as insertion sort.

Â [COUGH] the exchanges put the current element in to place among

Â the elements to its left.

Â And so, the cost of this sort or

Â number of exchanges is going to be the number of inversions in the permutation.

Â So we want to know how many inversions there are in a random permutation in

Â order to understand insertion sort.

Â 9:48

Cursive method like quick sort or merge sort when the files get small,

Â those methods are less efficient that insertion sort.

Â You want to switch to insertion sort.

Â You want to analyze the size that you need to switch to insertion sort,

Â you have to in order to be able to answer this question.

Â 10:21

but it's It's got the same transfer theorem and so forth as the star.

Â And it's just an indication of the kind

Â of freedom that we have in trying to understand combinatorial objects.

Â So in this construction, we're going to create a permutation.

Â They use a six pointed star.

Â The permutation of size n-1.

Â I'll create a permutation of the size n by inserting n in every possible position.

Â So here the 7 goes from the right most down to the 1st position.

Â Then there is no renumbering involved,

Â they all have the labels from 1 to 7 when you do that.

Â So, now you notice that when,

Â as we move from left to right, we add one more inversion.

Â So, the first one, this no additional inversions,

Â is the same number of inversions.

Â But then each one, as we move down, everybody to the right

Â of 7 gets one more inversion added because now 7 is to its left.

Â 11:30

And so we can calculate, again as before,

Â if we know the number of inversions in the original permutation.

Â And know the number of inversions in a set of constructive permutation and

Â it's there's all the inversions in the original still there

Â in the constructed permutations, but then we have all these additional inversions,

Â 1 plus 2 plus 3 up to the size of p, which is size of p plus 1 times p over 2.

Â So that's the number of inversions in the set of constructed perms.

Â Now, we're going to use that equation in our typical construction.

Â So now our accumulated generating function is on inversions and

Â again rearranging the size of the sum by size of

Â people if you want to group those that gives that equivalent

Â equation that we can now simplify

Â 12:33

It's got two terms in the first term the P+1 cancels against the P+1 pectorial.

Â In the second term the P+1, both in that one also the P+1 cancels.

Â So the first term is just ZB of Z.

Â In the second term, if you group by k,

Â it's just kz to the k because there's k factorial size and

Â there's an extra z to run out in the one half from pp plus one over two.

Â So now, that simple equation solved for b of z Is z B(z) + one half,

Â that generating function is the derivative of z to the k,

Â so z squared over (1- z) squared.

Â Now solve for B(z), and get another factor of one minus Z and

Â again it's one of our elementary generating functions.

Â Coefficient of Z to the N in that is the average number of immersions

Â is N times N minus one over four.

Â So, now that's the fourth and that's enough and

Â agin if want many more there's many more in the book.

Â Again, that checks against small values.

Â There's lots of properties and permutations that have been studied in

Â classical combinatorics that can be handled in a similar manner.

Â So for example, a rise in the permutations when the value goes up, but

Â falls when the value goes down.

Â A peak is when the value goes up and then down.

Â A valley is when the value goes down, then up.

Â A run is if you have successive values going up.

Â Left to right minima, we already talked about,

Â and increasing sub sequence is some subset of the permutation where

Â they go up all of these properties can be handled in a similar manner.

Â And again, the book contains several other derivations.

Â It wouldn't be productive to cover in lecture.

Â So those four indicate a an approach towards studying parameters

Â of permutations that's effective in those that we looked at

Â have actual applications to understanding the performance of

Â important algorithms in practical situations.

Â