1
00:00:00,012 --> 00:00:04,163
So next we're going to look at properties 
of permutations. 

2
00:00:04,163 --> 00:00:09,933
And as our main example we're going to 
talk about what's called left-to right 

3
00:00:09,933 --> 00:00:14,798
minima in permutations. 
So this is a parameter of permutations so 

4
00:00:14,798 --> 00:00:20,261
I, I want to talk some about the general 
approach that we use for analyzing 

5
00:00:20,261 --> 00:00:23,570
parameters. 
Now we talked about it last time for 

6
00:00:23,570 --> 00:00:26,919
trees. 
so we talked about leaves and random 

7
00:00:26,919 --> 00:00:31,855
binary trees last time, so we;re going to 
use the cuma, the accumulated cost 

8
00:00:31,855 --> 00:00:35,182
approach because we can use this symbolic 
method. 

9
00:00:35,182 --> 00:00:40,096
in a very straightforward manner so that, 
recall that we're going to define 

10
00:00:40,096 --> 00:00:45,295
generating functions for the counting 
sequence and for the accumulated cost and 

11
00:00:45,295 --> 00:00:49,640
then we're going to have a construction, 
and the construction will give an 

12
00:00:49,640 --> 00:00:54,956
equation, a generating function equation 
for the [UNKNOWN] Accumulated general 

13
00:00:54,956 --> 00:00:59,128
function. 
and then we're either going to solve to 

14
00:00:59,128 --> 00:01:06,542
get an explicit formula or find another 
way to extra coefficients to get the the 

15
00:01:06,542 --> 00:01:10,082
counting sequence and the accumulated 
cost. 

16
00:01:10,082 --> 00:01:15,130
and then we divide the accumulated cost 
by the counting sequence in order to get 

17
00:01:15,130 --> 00:01:18,830
the expected value. 
and we did that for leaves and binary 

18
00:01:18,830 --> 00:01:22,781
trees the last time. 
And that's the general approach 

19
00:01:22,781 --> 00:01:27,595
that we typically use in analytic common 
towards we'll see next time.to analyse 

20
00:01:27,595 --> 00:01:30,609
parameters. 
Now for permutations there's a small 

21
00:01:30,609 --> 00:01:33,472
trick. 
There's also a small trick for strings, 

22
00:01:33,472 --> 00:01:38,544
we'll see next time. 
And so first thing is we're going to use 

23
00:01:38,544 --> 00:01:43,578
exponential generating function for the 
cumulated cost. 

24
00:01:43,578 --> 00:01:50,021
So and it's exponential in the size, so 
it's the, we're going to consider the a 

25
00:01:50,021 --> 00:01:55,206
generating functions of the form b is z 
equals the sum over all permutations 

26
00:01:55,206 --> 00:02:00,391
whatever the cost of the parameter that 
where analyzing times the z to the size 

27
00:02:00,391 --> 00:02:06,318
of the permutation over the size 
factorial And that's again if you group 

28
00:02:06,318 --> 00:02:14,027
them by their size that's z will in over 
n factorial times of the costs, so, 

29
00:02:14,027 --> 00:02:19,232
exponential accumulating generating 
function. 

30
00:02:19,232 --> 00:02:27,570
Now what we'll do is treat that as an OGF 
to get the expected value out directly. 

31
00:02:27,570 --> 00:02:33,744
it's it's a little. 
So B sub n is the total accumulated cost 

32
00:02:33,744 --> 00:02:39,500
of, of that's the total cost for all 
[INAUDIBLE] users size N. 

33
00:02:39,500 --> 00:02:46,092
V sub N/N, is the average. 
so this works because n factorial is both 

34
00:02:46,092 --> 00:02:52,498
the normalizing factor and it's the 
counting sequence so really this is 

35
00:02:52,498 --> 00:02:57,567
shorthand for N times coefficient of z^N 
B(z) is the total cumulated cost. 

36
00:02:57,567 --> 00:03:03,467
N is also the counting sequence so if we 
just extract the coefficient of z^N we 

37
00:03:03,467 --> 00:03:08,117
get the average for permutations. 
so that's what we're going to do. 

38
00:03:08,117 --> 00:03:12,942
So we're going to work with the, an 
exponential cumulative generating 

39
00:03:12,942 --> 00:03:15,961
function. 
But then when it's time to extract 

40
00:03:15,961 --> 00:03:20,427
coefficients we'll just extract 
coefficients of z^N and immediately get 

41
00:03:20,427 --> 00:03:25,340
the average value of the parameter. 
so the application is an elementary 

42
00:03:25,340 --> 00:03:30,117
method known as selection sort. 
and it's takes quadratic time for any 

43
00:03:30,117 --> 00:03:34,751
order of permutations but it's the method 
of choice in some situations, for 

44
00:03:34,751 --> 00:03:39,702
example, when records are large and you 
can read about that in the algorithm. 

45
00:03:39,702 --> 00:03:44,327
In this a very simple algorithm that goes 
through from left to right. 

46
00:03:44,327 --> 00:03:49,102
The first thing it does is find the 
minimum element in the permutation, 

47
00:03:49,102 --> 00:03:53,952
exchanges that with the first. 
Then it finds the minimum in what remains 

48
00:03:53,952 --> 00:03:57,532
and exchanges that with the second. 
and so forth. 

49
00:03:57,532 --> 00:04:02,982
So first question is, how many times does 
a variable that keeps track of the 

50
00:04:02,982 --> 00:04:07,277
current minimum in this code. 
And the question is, how many times is 

51
00:04:07,277 --> 00:04:11,182
that variable updated assuming that all 
the keys. 

52
00:04:11,182 --> 00:04:17,997
[INAUDIBLE] So in this example we start 
out thinking that s is the minimum, o is 

53
00:04:17,997 --> 00:04:24,342
less so we update it r and t are bigger 
but i is less so we update it again. 

54
00:04:24,342 --> 00:04:30,991
g, e, and finally a is the fifth update. 
So for this permutation being this is 

55
00:04:30,991 --> 00:04:36,681
updated five times in the first pass. 
this quantity is called the number of 

56
00:04:36,681 --> 00:04:42,826
left or right minima in the permutation. 
so that's what we want to analyze first. 

57
00:04:42,826 --> 00:04:48,030
Now so, that's our question, how many 
left or right minima are there in a 

58
00:04:48,030 --> 00:04:52,775
random permutaton. 
now from a practical standpoint, this 

59
00:04:52,775 --> 00:04:58,166
question is, maybe less important than 
some of the others we talk about because 

60
00:04:58,166 --> 00:05:03,835
this cost is not significant compared to 
the number of compares but still it's a 

61
00:05:03,835 --> 00:05:08,282
fundamental property of permutations that 
we want to study. 

62
00:05:08,282 --> 00:05:14,470
So the left to right minima, or what we 
call an lrm, in the permutation, it's a 

63
00:05:14,470 --> 00:05:19,241
parameter, a permutation. 
And, it's an element that's smaller than 

64
00:05:19,241 --> 00:05:23,903
any item to it's left. 
So if a permutation begins with 1, like 

65
00:05:23,903 --> 00:05:29,370
the ones on the top in these examples, 
it's only got 1 left to right minima, the 

66
00:05:29,370 --> 00:05:31,795
1. 
If it begins with two. 

67
00:05:31,795 --> 00:05:35,096
It's got exactly two. 
The two and the one. 

68
00:05:35,096 --> 00:05:40,327
If it begins with three, it might have 
two, or it might have three. 

69
00:05:40,327 --> 00:05:45,085
And so forth. 
Permeatation in reverse order size N, has 

70
00:05:45,085 --> 00:05:48,977
n left to right minimum. 
Each new one is a minimum. 

71
00:05:48,977 --> 00:05:55,878
And so these tables in our standard form 
show for each permutaion, the number of 

72
00:05:55,878 --> 00:05:59,770
left to right mininima off to the, off to 
the side. 

73
00:05:59,770 --> 00:06:04,768
Then the total accumulated cost, is just 
summing those numbers. 

74
00:06:04,768 --> 00:06:10,833
Over for the three elements. 
You can later cross this two that crossed 

75
00:06:10,833 --> 00:06:15,059
one, three that crossed two, and one that 
crossed three. 

76
00:06:15,059 --> 00:06:20,290
So that's a total of 11. 
divide that by n, the average number of 

77
00:06:20,290 --> 00:06:25,288
left to right minima in a random 
permutation of size three is 1.833. 

78
00:06:25,288 --> 00:06:29,452
And similiarly for size four it's 2.883 
and so forth. 

79
00:06:29,452 --> 00:06:33,702
How many left to right minima in a random 
permutation of size N. 

80
00:06:33,702 --> 00:06:37,827
So that's our question. 
And again, it's usual, it's very 

81
00:06:37,827 --> 00:06:44,052
worthwhile to fully compute small values 
both to get an appreciation for the 

82
00:06:44,052 --> 00:06:50,252
intricacies of the problem and also to 
have precise values to check against when 

83
00:06:50,252 --> 00:06:54,682
we complete the analysis. 
so that's what this table is. 

84
00:06:54,682 --> 00:07:01,468
So what we're going to do is use a common 
notarial of construction to help us 

85
00:07:01,468 --> 00:07:08,747
derive directly a relationship that the 
accumulated generating function has to 

86
00:07:08,747 --> 00:07:12,655
satisfy. 
And that's the figuring out which 

87
00:07:12,655 --> 00:07:19,366
construction to use as the art of 
analytic common notaries for these kinds 

88
00:07:19,366 --> 00:07:23,145
of problems. 
So for left to right minima we're going 

89
00:07:23,145 --> 00:07:28,535
to use the star product construction. 
Where we say a permutation is a 

90
00:07:28,535 --> 00:07:34,286
permutation starred with an element. 
and that gives us a permuattion one 

91
00:07:34,286 --> 00:07:40,700
bigger to remembered in all consistent 
ways, and that just corresponds to 

92
00:07:40,700 --> 00:07:45,582
getting the last element the numbers form 
1, 1, though n+1. 

93
00:07:45,582 --> 00:07:51,867
and then renumbering the other elements 
in the permutation accordingly so now if 

94
00:07:51,867 --> 00:07:57,260
you look at the original permutation in 
this case has three left to right minima 

95
00:07:57,260 --> 00:08:01,955
the, all the permutations that we got 
from the star project have the same 

96
00:08:01,955 --> 00:08:07,073
number of left to right minima. 
With the exception of the first 1 has an 

97
00:08:07,073 --> 00:08:13,042
extra 1, which is the 1 at the end. 
So that construction and that observation 

98
00:08:13,042 --> 00:08:18,659
tells us if we, we know the number of 
left to right minima in the original 

99
00:08:18,659 --> 00:08:24,842
permutation, we know the number of left 
to right minima in all the permutations 

100
00:08:24,842 --> 00:08:31,004
that we constructed and that's this P+1 
of them and every one of them has the 

101
00:08:31,004 --> 00:08:34,134
same number of left or right minimums P 
did. 

102
00:08:34,134 --> 00:08:40,202
so those copies, and then, there's 1 
extra one the one that ends in 1. 

103
00:08:40,202 --> 00:08:44,820
That's a common notarial construction for 
permutations. 

104
00:08:44,820 --> 00:08:50,730
and then we're going to use that to 
derive a formula that the generating 

105
00:08:50,730 --> 00:08:54,822
function, the QA generating function has 
to satisfy. 

106
00:08:54,822 --> 00:08:59,377
P+1 error and then P+1. 
So to compute the average number of 

107
00:08:59,377 --> 00:09:05,012
left-right minima in random permutation. 
We define the accumulated generated 

108
00:09:05,012 --> 00:09:10,162
functoin which is the sum for every 
permuatation of its number of left to 

109
00:09:10,162 --> 00:09:14,097
right minima. 
*z to the size of our size factorial. 

110
00:09:14,097 --> 00:09:19,965
And again that if you group the 
permitations by their size, that gives 

111
00:09:19,965 --> 00:09:25,916
the accumulated cost, the exponential 
generating function for the cumulated 

112
00:09:25,916 --> 00:09:31,293
cost, which we dealt the 
so now if we apply the construction, 

113
00:09:31,293 --> 00:09:38,842
every permitation, of size, gives us p+1 
permitations so [COUGH] and the number of 

114
00:09:38,842 --> 00:09:45,182
left right minima in those permutations 
is size of p+1, [INAUDIBLE] p+1 size of 

115
00:09:45,182 --> 00:09:52,617
the permutations that we construct is 
z^p+1 so that applying that construction 

116
00:09:52,617 --> 00:09:59,254
immediate [INAUDIBLE]. 
Applies that equation on the generating 

117
00:09:59,254 --> 00:10:05,223
function. 
And that's an easy equation to simplify, 

118
00:10:05,223 --> 00:10:13,703
we, so the first term is size of p+1 
l*r*m of p, and that size of p+1 cancels 

119
00:10:13,703 --> 00:10:18,583
with size of p+1 factorial below size 
p+1. 

120
00:10:18,583 --> 00:10:24,924
So that gives us the first sum l*r*m of 
p*z*p+1 P factorial. 

121
00:10:24,924 --> 00:10:31,349
and then the second term in the plus one 
just throws out second term with z to 

122
00:10:31,349 --> 00:10:35,422
(p+1) over (p+1). 
So that's a simplification, now both of 

123
00:10:35,422 --> 00:10:40,030
those we can evaluate. 
The first one, and if you look up at the 

124
00:10:40,030 --> 00:10:47,193
first equation, is just a z B of Z. 
in the second one, if you group by size 

125
00:10:47,193 --> 00:10:53,134
of permeation just give Z to the K+1 over 
K factorial. 

126
00:10:53,134 --> 00:10:59,392
C^K+1 over K+1, which is K factorial 
permutations. 

127
00:10:59,392 --> 00:11:07,194
of size K, and that will cancel with the 
K+1 factorial, just leaving a K+1. 

128
00:11:07,194 --> 00:11:12,148
And that generating function is just log 
of 1/1-Z. 

129
00:11:12,148 --> 00:11:19,012
So now just solving for B of Z, we get B 
of Z equals 1/1-Z, log of 1/1-Z. 

130
00:11:19,012 --> 00:11:24,747
and remember that's the ordinary 
generating function, for the harmonic 

131
00:11:24,747 --> 00:11:28,227
number. 
And remember our trick for permutations 

132
00:11:28,227 --> 00:11:34,452
if we get, just extract the coefficient 
of z^n in that, then we get the b^n over 

133
00:11:34,452 --> 00:11:39,362
n, which is our average number of 
left-right minima and it's just the 

134
00:11:39,362 --> 00:11:45,082
harmonic number. 
so, a direct derivation of average number 

135
00:11:45,082 --> 00:11:51,472
of left-to-right minima using, 
combinatorial construction. 

136
00:11:51,472 --> 00:11:57,579
and it's a good idea to check those 
against the actual values that we 

137
00:11:57,579 --> 00:12:03,674
observed at the beginning, and sure 
enough, those were the harmonic numbers. 

138
00:12:03,674 --> 00:12:09,870
It's also possible to get the generating 
function equation through analytic 

139
00:12:09,870 --> 00:12:14,162
commonatorics /g, and ill talk about that 
in a minute. 

140
00:12:14,162 --> 00:12:21,361
but it's worthwhile to think in terms of 
these direct counting equations to we'll 

141
00:12:21,361 --> 00:12:27,022
worry about the analytic common torques 
and parameters a little bit. 

142
00:12:27,022 --> 00:12:33,059
Mostly in the 2nd part of the course. 
It's worthwhile to get a little bit of 

143
00:12:33,059 --> 00:12:39,255
experience working with it in this form 
to really have a feel for the power in 

144
00:12:39,255 --> 00:12:43,902
generality of a method. 
So that's left to right minimum. 

145
00:12:43,902 --> 00:12:49,646
now a similar question 
in terms of parameters on permutations. 

146
00:12:49,646 --> 00:12:56,352
suppose we want to know the number of 
cycles in a random permutation of size N. 

147
00:12:56,352 --> 00:13:02,593
And again if we look art this table, the 
number of cycles in each one of the 

148
00:13:02,593 --> 00:13:08,662
permutations is written to the left and 
we can go ahead and commute. 

149
00:13:08,662 --> 00:13:13,372
Compute the accumulated cost. 
and probably you've already recognized 

150
00:13:13,372 --> 00:13:17,317
that it's the same number. 
And so now we're going to look at why 

151
00:13:17,317 --> 00:13:21,002
it's the same number. 
So, to analyze the average number of 

152
00:13:21,002 --> 00:13:25,432
cycles in a random permutation, we'll use 
the same basic approach. 

153
00:13:25,432 --> 00:13:31,301
will look at a construction that creates 
a, that constructs permutations. 

154
00:13:31,301 --> 00:13:37,869
given one permutation construct of size 
n, construct n+1 of size n+1 and use that 

155
00:13:37,869 --> 00:13:44,009
construction to rearrange the terms of 
the sum of generating function to imply a 

156
00:13:44,009 --> 00:13:48,262
relationship that that generating 
function has to hold. 

157
00:13:48,262 --> 00:13:53,537
So for cycles, what we're going to do is, 
if we have a permutation that's set of 

158
00:13:53,537 --> 00:13:56,937
cycles, we're going to insert and it's of 
size N. 

159
00:13:56,937 --> 00:14:02,137
We're going to insert N plus 1 in every 
position in every cycle, including the 

160
00:14:02,137 --> 00:14:06,355
null cycle. 
so, first thing is, put 7 in the low 

161
00:14:06,355 --> 00:14:09,787
cycle, so that creates a new cycle of 
size 1. 

162
00:14:09,787 --> 00:14:15,594
and then put 7 in every position. 
And in the one cycle, there is only one 

163
00:14:15,594 --> 00:14:19,076
place that makes a 2 cycle, with 2 and 7 
in it. 

164
00:14:19,076 --> 00:14:24,842
and then in the 2 cycle, there's, 2 
places to put it, a 3,7,6 or 3,6,7. 

165
00:14:24,842 --> 00:14:34,840
and then the three cycle there's three 
places to put it, either 4715, 4175, or 

166
00:14:34,840 --> 00:14:40,258
4517. 
So that permutation of size 6 we can 

167
00:14:40,258 --> 00:14:47,150
strip 7 permutations of size seven. 
And so now the question is how many 

168
00:14:47,150 --> 00:14:53,659
cycles are there in all of these 
permutations? and so if, if the number of 

169
00:14:53,659 --> 00:14:57,022
cycles in the original perm is cycles of 
P. 

170
00:14:57,022 --> 00:15:01,718
Then how many are these in all of these. 
Well, they all have the same number of 

171
00:15:01,718 --> 00:15:06,866
cycles except the case where we added a 
new cycle by adding to the null cycle. 

172
00:15:06,866 --> 00:15:09,687
So there's P plus 1, copies the original 
perm. 

173
00:15:09,687 --> 00:15:14,601
They all have the same number of cycles. 
And then there's one extra for that extra 

174
00:15:14,601 --> 00:15:19,140
singleton cycle. 
So immediately now you can see, that's 

175
00:15:19,140 --> 00:15:24,823
exactly the same relationship that we had 
for left or right minimum. 

176
00:15:24,823 --> 00:15:30,130
And so what that means is, the 
derivation's going to be exactly the 

177
00:15:30,130 --> 00:15:34,351
same. 
so instead of lm I wrote cycles but it's 

178
00:15:34,351 --> 00:15:40,006
the very same derivation. 
we applied the construction and used to 

179
00:15:40,006 --> 00:15:43,751
that essentially re-order the terms in 
the sum. 

180
00:15:43,751 --> 00:15:48,852
And so then, the generating function also 
has to equal that 

181
00:15:48,852 --> 00:15:53,487
expression and then it simplifies in 
exactly the same way. 

182
00:15:53,487 --> 00:15:59,182
to get down to the harmonic number. 
Average number of cycles in a random 

183
00:15:59,182 --> 00:16:05,642
permutation of size N is H of N. 
Now when we have the same generating 

184
00:16:05,642 --> 00:16:13,807
function again often in combinatorics and 
when we see that what we'd like to do is 

185
00:16:13,807 --> 00:16:20,415
find a correspondence a [COUGH]. 
Between 1 to 1 correspondece between the 

186
00:16:20,415 --> 00:16:25,495
number of LRM and the number of cycles. 
So it's a reasonable question. 

187
00:16:25,495 --> 00:16:31,530
is there a 1 to 1 correspondence? and the 
ans, this is a famous one and the answer 

188
00:16:31,530 --> 00:16:35,023
is yes. 
so what you can do, if you have a set of 

189
00:16:35,023 --> 00:16:40,351
cycles you can build a permutation 
corresponding to that set of cycles, a 

190
00:16:40,351 --> 00:16:44,272
unique permutation corresponding to that 
set of cycles. 

191
00:16:44,272 --> 00:16:49,727
By looking at the smallest element in 
each cycle, we call that the leader of 

192
00:16:49,727 --> 00:16:55,205
the cycle, so the first one, the 4 is the 
leader, the second one the 1 is leader, 

193
00:16:55,205 --> 00:17:00,627
the [UNKNOWN] cycle there's only 1. 
the 3rd one the 14 is the leader, and the 

194
00:17:00,627 --> 00:17:04,538
last one the 2 is the leader. 
So we identified the leader of each 

195
00:17:04,538 --> 00:17:07,397
cycle. 
And then what we'll do is write down the 

196
00:17:07,397 --> 00:17:12,514
cycles in decreasing order of the leader. 
So we picked the largest leader, and then 

197
00:17:12,514 --> 00:17:15,967
write down it's cycle, just by following 
the cycle. 

198
00:17:15,967 --> 00:17:21,436
So in this case, the largest one is 14. 
And that's were we write 14, 16. 

199
00:17:21,436 --> 00:17:29,386
the next largest leader is just the 5. 
the next one is that 1st one which the 

200
00:17:29,386 --> 00:17:33,086
leader is 4, so we write down 4, 10, 6, 
15. 

201
00:17:33,086 --> 00:17:39,611
and then the big one at the end we write 
down 2, 12, 8, 3,11,13. 

202
00:17:39,611 --> 00:17:43,452
And then the one containing the 1, 1, 7, 
9. 

203
00:17:43,452 --> 00:17:49,519
Now we didn't right down, we didn't 
demark the cycles in any way but that's a 

204
00:17:49,519 --> 00:17:55,950
permeation and so, I said it was unique 
and that means we can use a corresponding 

205
00:17:55,950 --> 00:18:01,371
process, to get the set of cycles 
corresponding to any permeation. 

206
00:18:01,371 --> 00:18:07,984
What's the set of cycles corresponding to 
this set of permeation? So, we are given 

207
00:18:07,984 --> 00:18:12,481
the permeation.. 
What we do is, identify the left to right 

208
00:18:12,481 --> 00:18:14,897
minimum. 
Those are the leaders. 

209
00:18:14,897 --> 00:18:19,671
Remember, we picked the leader as the 
smallest in the cycle. 

210
00:18:19,671 --> 00:18:24,662
and then we wrote them down in decreasing 
order of the leaders. 

211
00:18:24,662 --> 00:18:30,870
so between each leader say between four 
and two everybody on the same cycle as 

212
00:18:30,870 --> 00:18:37,266
four is bigger and so the, as soon as we 
get somebody smaller than 4 that's the 

213
00:18:37,266 --> 00:18:43,282
leader of the next cycle So that's how we 
break up the permutation in to cycles and 

214
00:18:43,282 --> 00:18:48,912
that's immediately shows, that the number 
of left to right minima is equal to the 

215
00:18:48,912 --> 00:18:53,555
number of cycles, because this 
correspondence is 1 to 1, and works for 

216
00:18:53,555 --> 00:18:57,753
any permutation. 
so that's a, a famous correspondence 

217
00:18:57,753 --> 00:19:02,402
between left to right minima in cycles. 
that, so. 

218
00:19:02,402 --> 00:19:07,072
Now we can writedown the cycles just by 
finding the lrm. 

219
00:19:07,072 --> 00:19:12,747
And then simply writing these cycles out 
as before. 

220
00:19:12,747 --> 00:19:18,417
so that's a couple examples of paramters 
and permutations. 

221
00:19:18,417 --> 00:19:22,000
left-right-minima in number of cycles.