So next we're going to look at properties 
of permutations. 
And as our main example we're going to 
talk about what's called left-to right 
minima in permutations. 
So this is a parameter of permutations so 
I, I want to talk some about the general 
approach that we use for analyzing 
parameters. 
Now we talked about it last time for 
trees. 
so we talked about leaves and random 
binary trees last time, so we;re going to 
use the cuma, the accumulated cost 
approach because we can use this symbolic 
method. 
in a very straightforward manner so that, 
recall that we're going to define 
generating functions for the counting 
sequence and for the accumulated cost and 
then we're going to have a construction, 
and the construction will give an 
equation, a generating function equation 
for the [UNKNOWN] Accumulated general 
function. 
and then we're either going to solve to 
get an explicit formula or find another 
way to extra coefficients to get the the 
counting sequence and the accumulated 
cost. 
and then we divide the accumulated cost 
by the counting sequence in order to get 
the expected value. 
and we did that for leaves and binary 
trees the last time. 
And that's the general approach 
that we typically use in analytic common 
towards we'll see next time.to analyse 
parameters. 
Now for permutations there's a small 
trick. 
There's also a small trick for strings, 
we'll see next time. 
And so first thing is we're going to use 
exponential generating function for the 
cumulated cost. 
So and it's exponential in the size, so 
it's the, we're going to consider the a 
generating functions of the form b is z 
equals the sum over all permutations 
whatever the cost of the parameter that 
where analyzing times the z to the size 
of the permutation over the size 
factorial And that's again if you group 
them by their size that's z will in over 
n factorial times of the costs, so, 
exponential accumulating generating 
function. 
Now what we'll do is treat that as an OGF 
to get the expected value out directly. 
it's it's a little. 
So B sub n is the total accumulated cost 
of, of that's the total cost for all 
[INAUDIBLE] users size N. 
V sub N/N, is the average. 
so this works because n factorial is both 
the normalizing factor and it's the 
counting sequence so really this is 
shorthand for N times coefficient of z^N 
B(z) is the total cumulated cost. 
N is also the counting sequence so if we 
just extract the coefficient of z^N we 
get the average for permutations. 
so that's what we're going to do. 
So we're going to work with the, an 
exponential cumulative generating 
function. 
But then when it's time to extract 
coefficients we'll just extract 
coefficients of z^N and immediately get 
the average value of the parameter. 
so the application is an elementary 
method known as selection sort. 
and it's takes quadratic time for any 
order of permutations but it's the method 
of choice in some situations, for 
example, when records are large and you 
can read about that in the algorithm. 
In this 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 does 
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. 
[INAUDIBLE] So in this example we start 
out thinking that s is the minimum, o is 
less so we update it r and t are bigger 
but i is less so we update it again. 
g, e, and finally a is the fifth update. 
So for this permutation being this is 
updated five times in the first pass. 
this quantity is called the number of 
left or right minima in the permutation. 
so that's what we want to analyze first. 
Now so, that's our question, how many 
left or right minima are there in a 
random permutaton. 
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 the left to right minima, or what we 
call an lrm, in the permutation, it's a 
parameter, a permutation. 
And, it's an element that's smaller than 
any item to it's left. 
So if a permutation begins with 1, like 
the ones on the top in these examples, 
it's only got 1 left to right minima, the 
1. 
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. 
Permeatation in reverse order size N, has 
n left to right minimum. 
Each new one is a minimum. 
And so these tables in our standard form 
show for each permutaion, the number of 
left to right mininima off to the, off to 
the side. 
Then the total accumulated cost, is just 
summing those numbers. 
Over for the three elements. 
You can later cross this two that crossed 
one, three that crossed two, and one that 
crossed three. 
So that's a total of 11. 
divide that by n, the average number of 
left to right minima in a random 
permutation of size three is 1.833. 
And similiarly for size four it's 2.883 
and so forth. 
How many left to right minima in a random 
permutation of size N. 
So that's our question. 
And again, it's usual, it's very 
worthwhile 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 common 
notarial of construction to help us 
derive directly a relationship that the 
accumulated generating function has to 
satisfy. 
And that's the figuring out which 
construction to use as the art of 
analytic common notaries for these kinds 
of problems. 
So for left to right minima we're going 
to use the star product construction. 
Where we say a permutation is a 
permutation starred with an element. 
and that gives us a permuattion one 
bigger to remembered in all consistent 
ways, and that just corresponds to 
getting the last element the numbers form 
1, 1, though n+1. 
and then renumbering the other elements 
in the permutation accordingly so now if 
you look at the original permutation in 
this case has three left to right minima 
the, all the permutations that we got 
from the star project have the same 
number of left to right minima. 
With the exception of the first 1 has an 
extra 1, which is the 1 at the end. 
So that construction and that observation 
tells us if we, 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 this P+1 
of them and every one of them has the 
same number of left or right minimums P 
did. 
so those copies, and then, there's 1 
extra one the one that ends in 1. 
That's a common notarial construction for 
permutations. 
and then we're going to use that to 
derive a formula that the generating 
function, the QA generating function has 
to satisfy. 
P+1 error and then P+1. 
So to compute the average number of 
left-right minima in random permutation. 
We define the accumulated generated 
functoin which is the sum for every 
permuatation of its number of left to 
right minima. 
*z to the size of our size factorial. 
And again that if you group the 
permitations by their size, that gives 
the accumulated cost, the exponential 
generating function for the cumulated 
cost, which we dealt the 
so now if we apply the construction, 
every permitation, of size, gives us p+1 
permitations so [COUGH] and the number of 
left right minima in those permutations 
is size of p+1, [INAUDIBLE] p+1 size of 
the permutations that we construct is 
z^p+1 so that applying that construction 
immediate [INAUDIBLE]. 
Applies that equation on the generating 
function. 
And that's an easy equation to simplify, 
we, so the first term is size of p+1 
l*r*m of p, and that size of p+1 cancels 
with size of p+1 factorial below size 
p+1. 
So that gives us the first sum l*r*m of 
p*z*p+1 P factorial. 
and then the second term in the plus one 
just throws out second term with z to 
(p+1) over (p+1). 
So that's a simplification, now both of 
those we can evaluate. 
The first one, and if you look up at the 
first equation, is just a z B of Z. 
in the second one, if you group by size 
of permeation just give Z to the K+1 over 
K factorial. 
C^K+1 over K+1, which is K factorial 
permutations. 
of size K, and that will cancel with the 
K+1 factorial, just leaving a K+1. 
And that generating function is just log 
of 1/1-Z. 
So now just solving for B of Z, we get B 
of Z equals 1/1-Z, log of 1/1-Z. 
and remember that's the ordinary 
generating function, for the harmonic 
number. 
And remember our trick for permutations 
if we get, just extract the coefficient 
of z^n in that, then we get the b^n over 
n, which is our average number of 
left-right minima and it's just the 
harmonic number. 
so, a direct derivation of average number 
of left-to-right minima using, 
combinatorial construction. 
and it's a good idea to check those 
against the actual values that we 
observed at the beginning, and sure 
enough, those were the harmonic numbers. 
It's also possible to get the generating 
function equation through analytic 
commonatorics /g, and ill talk about that 
in a minute. 
but it's worthwhile to think in terms of 
these direct counting equations to we'll 
worry about the analytic common torques 
and parameters a little bit. 
Mostly in the 2nd part of the course. 
It's worthwhile to get a little bit of 
experience working with it in this form 
to really have a feel for the power in 
generality of a method. 
So that's left to right minimum. 
now a similar question 
in terms of parameters on permutations. 
suppose we want to know the number of 
cycles in a random permutation of size N. 
And again if we look art this table, the 
number of cycles in each one of the 
permutations is written to the left and 
we can go ahead and commute. 
Compute the accumulated cost. 
and probably you've already recognized 
that it's the same number. 
And 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. 
will look at a construction that creates 
a, that constructs permutations. 
given one permutation construct of size 
n, construct n+1 of size n+1 and use that 
construction to rearrange the terms of 
the sum of generating function to imply a 
relationship that that generating 
function has to hold. 
So for cycles, what we're going to do is, 
if we have a permutation that's set of 
cycles, we're going to insert and it's of 
size N. 
We're going to insert N plus 1 in every 
position in every cycle, including the 
null cycle. 
so, first thing is, put 7 in the low 
cycle, so that creates a new cycle of 
size 1. 
and then put 7 in every position. 
And in the one cycle, there is only one 
place that makes a 2 cycle, with 2 and 7 
in it. 
and then in the 2 cycle, there's, 2 
places to put it, a 3,7,6 or 3,6,7. 
and then the three cycle there's three 
places to put it, either 4715, 4175, or 
4517. 
So that permutation of size 6 we can 
strip 7 permutations of size seven. 
And so now the question is how many 
cycles are there in all of these 
permutations? and so if, if the number of 
cycles in the original perm is cycles of 
P. 
Then how many are these 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 1, copies the original 
perm. 
They all have the same number of cycles. 
And then there's one extra for that extra 
singleton cycle. 
So immediately now you can see, that's 
exactly the same relationship that we had 
for left or right minimum. 
And so what that means is, the 
derivation's going to be exactly the 
same. 
so instead of lm I wrote cycles but it's 
the very same derivation. 
we applied the construction and used to 
that essentially re-order the terms in 
the sum. 
And so then, the generating function also 
has to equal that 
expression and then it simplifies in 
exactly the same way. 
to get down to the harmonic number. 
Average number of cycles in a random 
permutation of size N is H of N. 
Now when we have the same generating 
function again often in combinatorics and 
when we see that what we'd like to do is 
find a correspondence a [COUGH]. 
Between 1 to 1 correspondece between the 
number of LRM and the number of cycles. 
So it's a reasonable question. 
is there a 1 to 1 correspondence? and the 
ans, this is a famous one and the answer 
is yes. 
so what you can 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, we call that the leader of 
the cycle, so the first one, the 4 is the 
leader, the second one the 1 is leader, 
the [UNKNOWN] cycle there's only 1. 
the 3rd one the 14 is the leader, and the 
last one the 2 is the leader. 
So we identified the leader of each 
cycle. 
And then what we'll do is write down the 
cycles in decreasing order of the leader. 
So we picked the largest leader, and then 
write down it's cycle, just by following 
the cycle. 
So in this case, the largest one is 14. 
And that's were we write 14, 16. 
the next largest leader is just the 5. 
the next one is that 1st one which the 
leader is 4, so we write down 4, 10, 6, 
15. 
and then the big one at the end we write 
down 2, 12, 8, 3,11,13. 
And then the one containing the 1, 1, 7, 
9. 
Now we didn't right down, we didn't 
demark the cycles in any way but that's a 
permeation 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 permeation. 
What's the set of cycles corresponding to 
this set of permeation? So, we are given 
the permeation.. 
What we do is, identify the left to right 
minimum. 
Those are the leaders. 
Remember, we picked 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 the, as soon as we 
get somebody smaller than 4 that's the 
leader of the next cycle So that's how we 
break up the permutation in to cycles and 
that's immediately shows, that the number 
of left to right minima is equal to the 
number of cycles, because this 
correspondence is 1 to 1, and works for 
any permutation. 
so that's a, a famous correspondence 
between left to right minima in cycles. 
that, so. 
Now we can writedown the cycles just by 
finding the lrm. 
And then simply writing these cycles out 
as before. 
so that's a couple examples of paramters 
and permutations. 
left-right-minima in number of cycles.