1 00:00:00,012 --> 00:00:06,468 Next, we'll look at 2 more examples of parameters in permutations. 2 00:00:06,468 --> 00:00:12,999 Again, just to gain some comfort with the basic method and also to, [COUGH] get 3 00:00:12,999 --> 00:00:18,167 more familiarity with the properties of permutation. 4 00:00:18,167 --> 00:00:25,886 And there's many, many other examples in the book, we're picking four parameters 5 00:00:25,886 --> 00:00:31,987 of permutations. And there's another [COUGH] 5 or 6 or 6 00:00:31,987 --> 00:00:38,537 more in the book. So say you want to know how many 1 cycles 7 00:00:38,537 --> 00:00:43,137 are there in a random permutation of size n. 8 00:00:43,137 --> 00:00:52,322 so for 2 the average number of 1 cycles is, is just 1 because the. 9 00:00:52,322 --> 00:00:57,982 permutation is 2 1-cycles since 2 and the, and the, and the one that's a 10 00:00:57,982 --> 00:01:02,437 2-cycle is 0. so the accumulated cost is 2 and divide 11 00:01:02,437 --> 00:01:07,212 by 2, we get 1. For 3 we have either 3 1-cycles, which is 12 00:01:07,212 --> 00:01:12,262 3 of the accumulated cost We have 3 of them that have 1-1 cycles. 13 00:01:12,262 --> 00:01:17,520 that adds another three to the cost. And so again, the total is Q at a cost is 14 00:01:17,520 --> 00:01:20,497 6. and then they're six of them, So the 15 00:01:20,497 --> 00:01:24,635 average is one. and you might start to see a pattern and 16 00:01:24,635 --> 00:01:30,009 sure enough for a permutation of size 4, the total accumulated cost, and you can 17 00:01:30,009 --> 00:01:35,546 count through it here there's 24 1 cycles and all these permutations and there's 24 18 00:01:35,546 --> 00:01:41,605 permutations so the average is 1. so we're going to expect a result to show 19 00:01:41,605 --> 00:01:47,245 that the number of 1-cycles average, expect the number of 1-cycles in a random 20 00:01:47,245 --> 00:01:52,362 permutation of size n is 1. and to show that we're going to use 21 00:01:52,362 --> 00:01:57,946 precisely the same construction, that we use, used for counting cycles. 22 00:01:57,946 --> 00:02:03,672 So, again, we put [p]+1 into every position in the cycle The difference in 23 00:02:03,672 --> 00:02:08,713 the analysis is if the original perm has cyc 1 of P1 cycles. 24 00:02:08,713 --> 00:02:12,810 How many are there in the set of constructed firms. 25 00:02:12,810 --> 00:02:17,592 Well the you have the same equation to start out with,. 26 00:02:17,592 --> 00:02:22,690 That is, there, whatever number of one-cycles there are, in the original 27 00:02:22,690 --> 00:02:27,794 there's, p+1 time set in all of these, but then we have to adjust to add the new 28 00:02:27,794 --> 00:02:32,152 one-cycle, when we added our new element to, make it a one-cycle. 29 00:02:32,152 --> 00:02:36,366 And then we have to subtract off for every one-cycle that was there. 30 00:02:36,366 --> 00:02:43,275 In this case, The two we knocked it out by making it into a two cycle in one of 31 00:02:43,275 --> 00:02:47,349 the perms. So we have to subtract off cyc 1 of p. 32 00:02:47,349 --> 00:02:54,087 So gives a slightly different formula. the number of 1-cycles in this set now is 33 00:02:54,087 --> 00:03:00,732 p*CYC1 of p+1, instead of p+1*CYC1 of p, so just that +1 is the difference between 34 00:03:00,732 --> 00:03:07,282 this equation and the one that we did for left to right minima and for cycles. 35 00:03:07,282 --> 00:03:13,389 So, let's look at what that happens to the analysis when, when we do that. 36 00:03:13,389 --> 00:03:17,477 so, CGF and then we apply the construction. 37 00:03:17,477 --> 00:03:22,939 And again, the only difference is, there's people have sworn before, and 38 00:03:22,939 --> 00:03:27,572 now, it's P. so now we don't have the ability to use 39 00:03:27,572 --> 00:03:34,212 the factor of p+1 to knock out the factor of p+1 in the denominator, p+1 factorial. 40 00:03:34,212 --> 00:03:40,069 We have to knock that out in a different way and the easy way to do that is, 41 00:03:40,069 --> 00:03:44,092 differentiate. So if we differentiate, Z to the P + 1 42 00:03:44,092 --> 00:03:50,060 over P +1 factorial, the P + 1 comes down and cancels and we just Z to the P over P 43 00:03:50,060 --> 00:03:53,822 factorial and then out two terms are immediate. 44 00:03:53,822 --> 00:04:02,269 And now the second one is just the EGF for permutations, that's 1 / 1 - z. 45 00:04:02,269 --> 00:04:12,722 in the first one the p cancels out and so that is the same, is just b prime and c. 46 00:04:12,722 --> 00:04:21,076 So if you take the derivative of B of z, if you look in the upper left, then first 47 00:04:21,076 --> 00:04:25,895 formula, the [COUGH] p cancels out with the p!. 48 00:04:25,895 --> 00:04:34,734 [COUGH], in the denominator, and then we're just left with an extra factor of 49 00:04:34,734 --> 00:04:38,282 z. So it's, it's z, p prime of z. 50 00:04:38,282 --> 00:04:43,633 in, then (+1/1-c), and, that's, our answer. 51 00:04:43,633 --> 00:04:50,963 So now we have a differential equation, B-prime(z)=1/1-z^2, and that's easy to 52 00:04:50,963 --> 00:04:56,982 solve, it's just, 1/1-z, And the coefficient z^n and that is, 1, 53 00:04:56,982 --> 00:05:02,392 so average number of one-cycles in a random permitation is 1. 54 00:05:02,392 --> 00:05:10,465 so, again, very straightforward, each step takes a little bit of experience to 55 00:05:10,465 --> 00:05:14,158 know. And how to differentiate and how to 56 00:05:14,158 --> 00:05:19,864 rearrange terms. but usually these tyupes of arguments are 57 00:05:19,864 --> 00:05:22,582 quite elementary. so 58 00:05:22,582 --> 00:05:30,067 For example, in our students and room problem, everyone goes back to a random 59 00:05:30,067 --> 00:05:37,682 room, what's the average number of people who wind up in their own room? Well, what 60 00:05:37,682 --> 00:05:43,567 we just proved is it's 1. Now, just to test yourself and your 61 00:05:43,567 --> 00:05:49,161 understanding of Of this method. It's worthwhile, maybe to take the time 62 00:05:49,161 --> 00:05:54,155 to try to figure out the number of, expected number of 2-cycles in a random 63 00:05:54,155 --> 00:05:59,479 permutation of size n, or, and generalize that to be expected number of r-cycles in 64 00:05:59,479 --> 00:06:04,622 a random permutation of size n. Now the answers are 1 / 2 and 1 / r and 65 00:06:04,622 --> 00:06:11,462 you can by solving these problems, you can see you'll get a little practice with 66 00:06:11,462 --> 00:06:16,852 manipulating these kinds of equations. As our last example of studying 67 00:06:16,852 --> 00:06:20,782 parameters in permutations, we'll look at inversion. 68 00:06:20,782 --> 00:06:26,157 An inverstion in a permutation is a pair that's out of order. 69 00:06:26,157 --> 00:06:33,096 That's a little bit imprecise, a better way to look at it is just to say it's the 70 00:06:33,096 --> 00:06:39,717 sum of the For each entry we sum up the number of elements that are larger and to 71 00:06:39,717 --> 00:06:44,032 the left. so for example in the top right corner 72 00:06:44,032 --> 00:06:48,732 1,2,4,3 the only pair that is out of order is 3 and 4. 73 00:06:48,732 --> 00:06:54,289 so, three has one larger element to its left before, all the rest of them have 74 00:06:54,289 --> 00:06:59,105 zero larger elements to the left. The one below 2 1 4 3 has two inversion. 75 00:06:59,105 --> 00:07:02,489 One and two and three and four are out of order. 76 00:07:02,489 --> 00:07:08,032 One has one larger element to its left, three has one larger element to its left. 77 00:07:08,032 --> 00:07:13,114 On the one below that, 3,1,4,2, That one has three inversions. 78 00:07:13,114 --> 00:07:17,302 because 1 has 1 larger element.to its left of three. 79 00:07:17,302 --> 00:07:21,482 And 2 has 2 larger elements to its left, the 4 and 3. 80 00:07:21,482 --> 00:07:26,188 And again for every one of these permutations, we have written down off to 81 00:07:26,188 --> 00:07:30,944 the side the number of inversions. If you add all those numbers up, you get 82 00:07:30,944 --> 00:07:34,798 the accumulated cost. for 3, the accumulated cost is 9. 83 00:07:34,798 --> 00:07:37,692 So the average number of inversions is 1 1/2. 84 00:07:37,692 --> 00:07:41,435 for 4. the total accumulated cost is 72. 85 00:07:41,435 --> 00:07:45,638 So the average, so the accumulated cost is 72. 86 00:07:45,638 --> 00:07:52,626 And expected number of inversions is 3. so, that's the quantity we want to study 87 00:07:52,626 --> 00:07:58,694 that number of inversions. An application of this is, to analyze, 88 00:07:58,694 --> 00:08:03,682 another elementary sorting algorithm called insertion sort. 89 00:08:03,682 --> 00:08:08,032 and that's also the method of choice in some situations. 90 00:08:08,032 --> 00:08:14,082 We can read about it in algorithms. and so understanding it's performance for 91 00:08:14,082 --> 00:08:18,462 random permutation is is useful in practical situation. 92 00:08:18,462 --> 00:08:25,586 so what insertion sort does is it goes through the for every position i, it's 93 00:08:25,586 --> 00:08:30,327 job is to keep all the elements before i in sorted order. 94 00:08:30,327 --> 00:08:36,825 And the way that it does that is when it gets a new element it exchanges it with 95 00:08:36,825 --> 00:08:43,441 all the larger elements to its left. so in this case, when i =10 and. 96 00:08:43,441 --> 00:08:48,570 Pointing at the m it knows that everything to its left is already sorted 97 00:08:48,570 --> 00:08:54,073 but looking at the current element it's elements to its left is larger, so we 98 00:08:54,073 --> 00:08:57,806 exchange. We keep exchanging as long as the element 99 00:08:57,806 --> 00:09:02,069 to its left is larger. So ram is still always larger and N is 100 00:09:02,069 --> 00:09:07,592 larger and when it gets to a point where the element to its left is smaller. 101 00:09:07,592 --> 00:09:11,517 Then it's inserted into its proper place in the array. 102 00:09:11,517 --> 00:09:17,442 so, that's known as insertion sort. [COUGH], the exchanges put the current 103 00:09:17,442 --> 00:09:21,292 element into place among the elements to it's left. 104 00:09:21,292 --> 00:09:26,517 And so the cost of this sort and the number of exchanges is going to be the 105 00:09:26,517 --> 00:09:31,942 number of inversions in the permutation. So, we want to know how many inversions 106 00:09:31,942 --> 00:09:36,642 there are in a random permutation in order to understand insertions. 107 00:09:36,642 --> 00:09:43,479 So for example, insertion sort is, often used in practice, as, when you use quick 108 00:09:43,479 --> 00:09:49,723 sort, a recursive method like quick sort or merge sort, when the files get small, 109 00:09:49,723 --> 00:09:53,536 those methods are less efficient than insertion sort. 110 00:09:53,536 --> 00:09:58,694 So want to switch to insertion sort. Want to analyze the size at you should 111 00:09:58,694 --> 00:10:04,759 switch to insertion sort, you have to, Be able to answer this question. 112 00:10:04,759 --> 00:10:10,244 So that's an insertion sort. So what's the construction for inversion? 113 00:10:10,244 --> 00:10:14,192 So now we're going to use a different construction. 114 00:10:14,192 --> 00:10:19,677 I didn't, mention this one as one of the basic constructions for analytic 115 00:10:19,677 --> 00:10:25,851 combinatorics, but it's got the same transfer theorem and, and so forth, is 116 00:10:25,851 --> 00:10:29,718 the star. and it's just an indication of; of the 117 00:10:29,718 --> 00:10:35,810 kind of freedom that we have in trying to understand combinatorial objects. 118 00:10:35,810 --> 00:10:42,387 So in this construction we're going to create a permutation that uses 6-point 119 00:10:42,387 --> 00:10:46,034 star. Permutation of size N-1, I'll create a 120 00:10:46,034 --> 00:10:50,978 permutation of size N by inserting N in every possible position. 121 00:10:50,978 --> 00:10:55,886 So here the 7 goes from the rightmost down to the first position. 122 00:10:55,886 --> 00:11:01,876 Then there's no renumbering involved, they all have the labels from 1 to 7 when 123 00:11:01,876 --> 00:11:06,922 you do that. so, now you notice that when as we move 124 00:11:06,922 --> 00:11:10,679 from left to right, we add 1 more inversion. 125 00:11:10,679 --> 00:11:16,962 so it, the first one, there's no additional inversions, that's the same 126 00:11:16,962 --> 00:11:23,785 number of inversions, but then each one as we, as we move down, everybody to the 127 00:11:23,785 --> 00:11:30,122 right of 7 It gets one more inversion added because now 7 is to its left. 128 00:11:30,122 --> 00:11:36,947 So we can calculate, again as before if we know the number of inversions of the 129 00:11:36,947 --> 00:11:43,372 original permutations then we know the number of inversions in the set of 130 00:11:43,372 --> 00:11:49,947 constructed permutations and it's, there's, All the inversions in the 131 00:11:49,947 --> 00:11:54,942 original are still there in the constructed permentations but then we 132 00:11:54,942 --> 00:12:00,402 have all these additional inversions 1 + 2 + 3 up to size of P which is size of P 133 00:12:00,402 --> 00:12:05,626 + 1 x P over 2 So those number of inversions in the set of constructed 134 00:12:05,626 --> 00:12:09,258 perms. Now we're going to use that equation in 135 00:12:09,258 --> 00:12:14,022 our typical construction. So now our accumulated generated 136 00:12:14,022 --> 00:12:19,306 functions is on inversions. And again rearranging the sizes of the 137 00:12:19,306 --> 00:12:25,199 sum by size of P+1 and grouping those together gives us that equivelant 138 00:12:25,199 --> 00:12:31,240 equation. that we can now simplify it's got 2 139 00:12:31,240 --> 00:12:35,706 terms. In the first term, the P+1 cancels. 140 00:12:35,706 --> 00:12:43,372 Again, the P begets the P+1 factorial. In the second term the P+1 in 141 00:12:43,372 --> 00:12:49,639 Both in that one also, will both cancel. So, The 1st term is just zb^z. 142 00:12:49,639 --> 00:12:57,293 And, the 2nd term if you group by k, it's just kz^k, because there's k factorial 143 00:12:57,293 --> 00:13:03,609 sides, and there's extra z thrown out, in the 1/2, from p+1/2. 144 00:13:03,609 --> 00:13:11,618 so that simple equation solve for b of z is z, z, b of z +1/2, that generating 145 00:13:11,618 --> 00:13:17,627 function is just derivative of z^k. So it's z^2/1-z^2. 146 00:13:17,627 --> 00:13:22,748 now solve for b of z. And given the factor of 1-c. 147 00:13:22,748 --> 00:13:29,959 And again, that's one of our most elementary generating functions [z^n] and 148 00:13:29,959 --> 00:13:33,739 that is the average number of conversions is N(N-1)/4. 149 00:13:35,803 --> 00:13:40,034 So that's the fourth derivation and that's enough. 150 00:13:40,034 --> 00:13:45,103 And again, if you want many more there's many more in the book. 151 00:13:45,103 --> 00:13:49,192 this again that checks against small values. 152 00:13:49,192 --> 00:13:53,791 there's lots of properties of permutations that have been studied in 153 00:13:53,791 --> 00:13:57,919 classical combinatorics and that can be handled in a similar manner. 154 00:13:57,919 --> 00:14:01,949 So, for example a rise in the permutation is when the value goes up. 155 00:14:01,949 --> 00:14:06,734 A fall is when the value goes down. A peak is when the value goes up and then 156 00:14:06,734 --> 00:14:09,897 down. A valley is when the value goes down then 157 00:14:09,897 --> 00:14:13,489 up. A run is if you have, successive, values 158 00:14:13,489 --> 00:14:17,436 going up. left to right minima, we already talked 159 00:14:17,436 --> 00:14:20,302 about. And increasing subsequence. 160 00:14:20,302 --> 00:14:25,107 Is some subset of the permutation where they go up. 161 00:14:25,107 --> 00:14:30,047 And all of these properties can be handled in a similar manner. 162 00:14:30,047 --> 00:14:36,362 and, and again, the book contains several other derivations it wouldn't be 163 00:14:36,362 --> 00:14:42,781 productive to cover in lecture. but, so those four indicate a an approach 164 00:14:42,781 --> 00:14:48,875 toward studying parameters of permutation that's effective and those that we looked 165 00:14:48,875 --> 00:14:53,384 at have actual applications to understanding the performance of 166 00:14:53,384 --> 00:14:56,857 important algorithms in in practical situations.