Tip:
Highlight text to annotate it
X
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.