Next, we'll look at 2 more examples of 
parameters in permutations. 
Again, just to gain some comfort with the 
basic method and also to, [COUGH] get 
more familiarity with the properties of 
permutation. 
And there's many, many other examples in 
the book, we're picking four parameters 
of permutations. 
And there's another [COUGH] 5 or 6 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 2 the average number of 1 cycles 
is, is just 1 because the. 
permutation is 2 1-cycles since 2 and 
the, and the, and the one that's a 
2-cycle is 0. 
so the accumulated cost is 2 and divide 
by 2, we get 1. 
For 3 we have either 3 1-cycles, which is 
3 of the accumulated cost We have 3 of 
them that have 1-1 cycles. 
that adds another three to the cost. 
And so again, the total is Q at a cost is 
6. 
and then they're six of them, So the 
average is one. 
and you might start to see a pattern and 
sure enough for a permutation of size 4, 
the total accumulated cost, and you can 
count through it here there's 24 1 cycles 
and all these permutations and there's 24 
permutations so the average is 1. 
so we're going to expect a result to show 
that the number of 1-cycles average, 
expect the number of 1-cycles in a random 
permutation of size n is 1. 
and to show that we're going to use 
precisely the same construction, that we 
use, used for counting cycles. 
So, again, we put [p]+1 into every 
position in the cycle The difference in 
the analysis is if the original perm has 
cyc 1 of P1 cycles. 
How many are there in the set of 
constructed firms. 
Well the you have the same equation to 
start out with,. 
That is, there, whatever number of 
one-cycles there are, in the original 
there's, p+1 time set 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 cyc 1 of p. 
So gives a slightly different formula. 
the number of 1-cycles in this set now is 
p*CYC1 of p+1, instead of p+1*CYC1 of p, 
so just that +1 is the difference between 
this equation and the one that we did for 
left to right minima and for cycles. 
So, let's look at what that happens to 
the analysis when, when we do that. 
so, CGF and then we apply the 
construction. 
And again, the only difference is, 
there's people have sworn before, and 
now, it's P. 
so now we don't have the ability to use 
the factor of p+1 to knock out the factor 
of p+1 in the denominator, p+1 factorial. 
We have to knock that out in a different 
way and the easy way to do that is, 
differentiate. 
So if we differentiate, Z to the P + 1 
over P +1 factorial, the P + 1 comes down 
and cancels and we just Z to the P over P 
factorial and then out two terms are 
immediate. 
And now the second one is just the EGF 
for permutations, that's 1 / 1 - z. 
in the first one the p cancels out and so 
that is the same, is just b prime and c. 
So if you take the derivative of B of z, 
if you look in the upper left, then first 
formula, the [COUGH] p cancels out with 
the p!. 
[COUGH], in the denominator, and then 
we're just left with an extra factor of 
z. 
So it's, it's z, p prime of z. 
in, then (+1/1-c), and, that's, our 
answer. 
So now we have a differential equation, 
B-prime(z)=1/1-z^2, and that's easy to 
solve, it's just, 1/1-z, 
And the coefficient z^n and that is, 1, 
so average number of one-cycles in a 
random permitation is 1. 
so, again, very straightforward, each 
step takes a little bit of experience to 
know. 
And how to differentiate and how to 
rearrange terms. 
but usually these tyupes of arguments are 
quite elementary. 
so 
For example, in our students and room 
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 it's 1. 
Now, just to test yourself and your 
understanding of Of this method. 
It's worthwhile, maybe to take the time 
to try to figure out the number of, 
expected number of 2-cycles in a random 
permutation of size n, or, and generalize 
that to be expected number of r-cycles in 
a random permutation of size n. 
Now the answers are 1 / 2 and 1 / r and 
you can by solving these problems, you 
can see you'll get a little practice with 
manipulating these kinds of equations. 
As our last example of studying 
parameters in permutations, we'll look at 
inversion. 
An inverstion in a permutation is a pair 
that's out of order. 
That's a little bit imprecise, a better 
way to look at it is just to say it's the 
sum of the For each entry we sum up the 
number of elements that are larger and to 
the left. 
so for example in the top right corner 
1,2,4,3 the only pair that is out of 
order is 3 and 4. 
so, three has one larger element to its 
left before, all the rest of them have 
zero larger elements to the left. 
The one below 2 1 4 3 has two inversion. 
One and two and three and four are out of 
order. 
One has one larger element to its left, 
three has one larger element to its left. 
On the one below that, 3,1,4,2, That one 
has three inversions. 
because 1 has 1 larger element.to its 
left of three. 
And 2 has 2 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 accumulated cost. 
for 3, the accumulated cost is 9. 
So the average number of inversions is 1 
1/2. 
for 4. 
the total accumulated cost is 72. 
So the average, so the accumulated cost 
is 72. 
And expected number of inversions is 3. 
so, that's the quantity we want to study 
that 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. 
We can read about it in algorithms. 
and so understanding it's performance for 
random permutation is is useful in 
practical situation. 
so what insertion sort does is it goes 
through the for every position i, it's 
job is to keep all the elements before i 
in sorted 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. 
so in this case, when i =10 and. 
Pointing at the m it knows that 
everything to its left is already sorted 
but looking at the current element it's 
elements to its left is larger, so we 
exchange. 
We keep exchanging as long as the element 
to its left is larger. 
So ram is still always larger and N is 
larger and when it gets to a point where 
the element to its left is smaller. 
Then it's inserted into its proper place 
in the array. 
so, that's known as insertion sort. 
[COUGH], the exchanges put the current 
element into place among the elements to 
it's left. 
And so the cost of this sort and the 
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 insertions. 
So for example, insertion sort is, often 
used in practice, as, when you use quick 
sort, a recursive method like quick sort 
or merge sort, when the files get small, 
those methods are less efficient than 
insertion sort. 
So want to switch to insertion sort. 
Want to analyze the size at you should 
switch to insertion sort, you have to, 
Be able to answer this question. 
So that's an insertion sort. 
So what's the construction for inversion? 
So now we're going to use a different 
construction. 
I didn't, mention this one as one of the 
basic constructions for analytic 
combinatorics, but it's got the same 
transfer theorem and, and so forth, is 
the star. 
and it's just an indication of; 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 that uses 6-point 
star. 
Permutation of size N-1, I'll create a 
permutation of size N by inserting N in 
every possible position. 
So here the 7 goes from the rightmost 
down to the first position. 
Then there's 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 1 more 
inversion. 
so it, the first one, there's no 
additional inversions, that's the same 
number of inversions, but then each one 
as we, as we move down, everybody to the 
right of 7 It gets one more inversion 
added because now 7 is to its left. 
So we can calculate, again as before if 
we know the number of inversions of the 
original permutations then we know the 
number of inversions in the set of 
constructed permutations and it's, 
there's, All the inversions in the 
original are still there in the 
constructed permentations but then we 
have all these additional inversions 1 + 
2 + 3 up to size of P which is size of P 
+ 1 x P over 2 So those 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 generated 
functions is on inversions. 
And again rearranging the sizes of the 
sum by size of P+1 and grouping those 
together gives us that equivelant 
equation. 
that we can now simplify it's got 2 
terms. 
In the first term, the P+1 cancels. 
Again, the P begets the P+1 factorial. 
In the second term the P+1 in 
Both in that one also, will both cancel. 
So, The 1st term is just zb^z. 
And, the 2nd term if you group by k, it's 
just kz^k, because there's k factorial 
sides, and there's extra z thrown out, in 
the 1/2, from p+1/2. 
so that simple equation solve for b of z 
is z, z, b of z +1/2, that generating 
function is just derivative of z^k. 
So it's z^2/1-z^2. 
now solve for b of z. 
And given the factor of 1-c. 
And again, that's one of our most 
elementary generating functions [z^n] and 
that is the average number of conversions 
is N(N-1)/4. 
So that's the fourth derivation and 
that's enough. 
And again, if you want many more there's 
many more in the book. 
this again that checks against small 
values. 
there's lots of properties of 
permutations that have been studied in 
classical combinatorics and that can be 
handled in a similar manner. 
So, for example a rise in the permutation 
is when the value goes up. 
A fall is 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 subsequence. 
Is some subset of the permutation where 
they go up. 
And all of these properties can be 
handled in a similar manner. 
and, and again, the book contains several 
other derivations it wouldn't be 
productive to cover in lecture. 
but, so those four indicate a an approach 
toward studying parameters of permutation 
that's effective and those that we looked 
at have actual applications to 
understanding the performance of 
important algorithms in in practical 
situations.