This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
BGFs and Distributions
Loading...
Del curso dictado por Princeton University
Analysis of Algorithms
37 calificaciones
De la lección
Permutations
The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.
Conoce a los instructores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
So now I want to finish up this lecture by giving an indication of how these kinds
of problems can be solved with analytic combinatorics in the symbolic method.
Essentially, those derivations, in a sense,
were a little bit the hard way, and there's an easier way.
Now we'll develop this fully in Part Two, but
it's worthwhile to take a look at a typical derivation using analytic
combinatorics because it's actually not that much more difficult.
And actually, the idea is to use bivariate generating functions.
That's really the way to analyze combinatorial parameters.
So the idea is, for a combinatorial class, we have not just the size function, but
we also have an associated parameter that has a cost.
And we want to analyze the cost associated with the size.
We're looking for the average number of cycles in all permutations of size n,
and so forth.
So the way that we do that, say for unlabeled objects, is to just
take another variable, u, and to find the bivariate generating function,
z and u, where z is for size and u is for cost.
So for every object, we take z to the size of that object and
u to the cost of that object.
So that's what we work with for labeled classes.
We divide by the size factorial, but it's the same idea.
So that's the form that we're going to work with for permutations.
Now, the idea is that those constructions that we gave are going to work
just as well to give us formulas that these bivariate generating functions have
to satisfy.
And not only that, the bivariate generating function really does carry
full information about the association between size and cost.
And again, it's pretty much as easy to compute as the CGF.
And we'll look at those computations next.
And not only that, using this approach with analytic combinatorics,
it's often the case that we can get full distribution or
the asymptotics of the full distribution by knowing and
generating a formula that the bivariate generating function has to satisfy.
So it's extension of the symbolic method beyond just counting to also
take into account cost of parameters in combinatorial structures.
So what are the basic calculations?
So we start with a bivariate generating function.
And this is exponential for labelled classes like permutations because that's
all the examples I've done so far today.
So if you want to go back to the way that maybe you're used to thinking
of things, and we had in our tables, actually,
the number of elements of size N with parameter value k,
then [COUGH] you have the fundamental identity
which just extends what we did for single variate generating functions.
If you're summing in all combinatorial objects,
you can gather them together by size and by cost.
And then the number with [COUGH] size N and cost k,
that's the coefficient of z to the N / N factorial u to the k
because every one of those objects will contribute one to the sum.
You gather them together, you ANk objects that have that sum.
And so that identity is implicit.
When we're trying to understand the combinatorics of it,
we work with the representation where we have a term in the sum for every object.
But when we want to do some counting, we use the elementary
identity to get us the results that we need.
So, for example, as I just said, the number of objects
of size N with value k, we can get from the bivariate generating function.
It's the coefficient of z to the N coefficient of u to the k multiplied by N
factorial for label.
So what's interesting is,
what's the average value of a parameter for a permutation?
It's the coefficient of z to the N in the partial derivative of
the bivariate generating function with respect to u evaluated at u = 1.
It seems like maybe a strange operation to perform but
that calculation is really simple.
So if you take the partial of A(z,u) with respect to u, you get k u to the k- 1.
So now if you evaluate that at u = 1, then the u to the k- 1 goes away.
And now if you look at that sum, what's the coefficient of z to the N in that?
It's the sum of k ANk.
And then, again, the trick, the divide by N factorial.
So it's the sum of k, the probability that it's k, which is exactly the average.
So just knowing that one
little really trivial calculation means that we can go ahead and
[COUGH] use our constructions to tell us about the bivariate generating function
and just do that one, differentiate with respect to u and evaluate at u = 1.
So this is the construction that we did earlier on, say,
for average number of cycles.
And this is the same slide as above so
I won't spend too much time talking about it.
So we apply our construction and
then simplify the sum to get down to the harmonic numbers.
So let's do it with bivariate generating functions.
So bivariate generating function,
it's z to the size over size factorial u to the cost.
So now our same construction, which has
[COUGH] for every permutation,
we construct a bunch of other ones, and
p of those have the same number of cycles and one of them has one more cycle.
So that's what this equation says, those permutations of size p + 1.
One of them has one more cycle, so that's u to the cycles of p + 1,
and p of them have the same number of cycles, so that's u to the cycles of p.
So rearranging the terms and the sum according to this construction
implies that identity on the bivariate generating function.
And that one is not so
difficult to [COUGH] simplify.
So z to the p + 1 / (p + 1) factorial,
that means we should differentiate with respect to z.
And if we do that, then we get two simple sums that we can easily simplify.
The first one is just uB(z,u) and
the second one is like the derivative with an extra factor of z.
And you could check that.
That's a very simple calculation.
Now we can solve for derivative of u with respect to z.
And we have B sub z (z,u) = u / 1- z B(z,u).
Now that's a differential equation in z that we can just solve,
and it's 1 / (1- z) to the u.
And it's a little shocking at first that there should
be such a simple solution, but once you think of u as a constant and
just work with the z, it's not so amazing a calculation.
And that's an explicit formula for B bivariate generating function.
And what do we want from that formula?
What we want is the average value of our parameter.
How do we get the average value of that parameter?
For any bivariate generating function,
all we do is differentiate with respect to u and evaluate at u = 1.
Differentiate that with respect to u,
evaluate at u = 1, you get 1 / 1- z log 1 / 1- z.
That and the coefficient of z to the N in that is your average,
which is a harmonic number.
So the same kind of construction leads us to our result.
But what really makes bivariate generating functions the method
of choice is that we can actually get rid of this construction stuff and
really use the symbolic method.
And again, we'll talk about many examples of this later on, but
I want to show it for this one.
So the idea is to just carry the cost along with the combinatorial
constructions, and the transfer theorems and
everything else follow right through for
bivariate [COUGH] without much difficulty at all.
So the symbolic method will take us right to where we need to get.
So this says, a permutation is a set of cycles of Z,
and the variable u marks the number of cycles, and that's it.
So that immediately leads through transfer
theorem which is the same cycle as log of
1 / 1- z and set as e to the power, and
immediately leads to e to the u log of 1 / 1- z.
So a simple combinatorial construction immediate transfer to BGF equation.
And there we are, no sums at all.
And what do we want?
We want to differentiate with respect to u, evaluate at u = 1.
And in this form, it's the same function that's 1 / 1- z to the u,
just written in the exp log form.
It's obvious that the derivative with respect to u
is going to bring out a factor of log 1- z.
And then leave this term, evaluate at u = 1, just 1 / 1- z.
So immediate from the transfer theorem to there, and then immediate
derivative evaluated at u = 1, which immediately gives our harmonic numbers.
So derivations of this simplicity replacing the ones we've been doing
is really persuasive evidence or persuasive bottom line that BGFs and
the symbolic method are the method of choice in analyzing parameters.
We're going to see many examples of that in Part Two.
So here is a setting another example.
So you wanted to know the average number of cycles of size,
one that we did the exercise with two and r, and so forth.
So here is that derivation using a symbolic method.
So a number of cycles of size r.
Well, it's a set of cycles that are not of size r plus cycles that are size r
marked with the cost variable u, and that's it.
And so by transfer theorem,
that immediately gives log of 1- z with the 1 for
r subtracted off, and then add it back on, marked with u.
So immediate from the transfer theorem to that BGF equation.
And then what's the value we're interested in?
We want to differentiate with respect to u, evaluate at u = 1.
And that is immediate,
differentiate with respect to u brings up to the z to the r over r,
evaluate at u = 1 just makes it e to the log of 1 / 1- z,
and that's the generating function for the average number of cycles.
And what's the coefficient of z to the N in that?
It's 1 / r as long as N is bigger or equal to r.
So working with the constructions in the way we did
earlier is at the level of detail that analytic combinatorics can free us from.
And again, we'll see many more examples of working
with parameters that allow us to use the symbolic method for
bivariate generating functions in this way.
[COUGH] So that'll be mostly in Part Two.
And just to quickly finish up without going into much detail, this parameter,
the number of permutations with size N with k cycles has got a long history and
lots of applications that we don't have the time to talk about in detail.
So it's called Stirling numbers of the first kind and
it's usually written nowadays in square brackets like that.
So for permutations of size 3, there's 2 of them that have 1 cycle,
3 of them that have 2 cycles, and 1 of them that has 3 cycles.
And for 4 goes 6, 11, 6, and 1, and so forth.
So what we just did was show that [COUGH] if we just define the BGF for
Stirling numbers of the first kind,
we just showed that it's 1 / 1- z to the u.
And you can use that form to develop all kinds of interesting identities for
the Stirling number.
For example, the distribution for a given N,
the number of cycles of size N [COUGH] is
the coefficient of z to the N / N factorial, which,
if you use Taylor's theorem to expand this,
you get u times (u + 1), (u + N- 1), and so forth.
So if you take that polynomial in u, the coefficients of that
polynomial give you the Stirling numbers of the second kind.
And you can also come up with a way to compute them and get a recursive
formula like the basic formula for binomial coefficients and so forth.
We'll come back to some more details about this in Part Two.
I just wanted to point out that this kind of structure,
in more detail, has been studied a great deal.
In fact, here's a distribution with rescaling by N,
and actually one of the results in combinatorics
we studied tried to learn about limiting
distributions in situations like this.
And actually it can show that this distribution is normal in certain ranges.
So that's the use of bivariate generating functions, and an introduction
of an easier way to deal with analysis of parameters in permutations.
So I just want to finish up by pointing out a couple
of exercises that people could do to test their understanding of the material that
we've talked about so far.
So the first one is this study, arrangements.
So an arrangement of N elements is a sequence formed by a subset of
the elements.
So that's a permutation of each element once and only once.
With arrangement, you could use some of them more often.
And so the problem is to study arrangements
and to get some kind of combinatorial interpretation.
This next one tests two different concepts
that we've brought up and that's inversions and involutions.
So find the average number of inversions in an involution.
And there's no real reason to do that other than to test out the mathematics.
And then the third problem gets at what does the cycle length
distribution look like.
So it actually turns out to be asymptotic to a Poisson distribution.
And from the generating functions, you can show that.
It's an interesting problem to work through.
So, for next lecture, read the [COUGH] Chapter Seven in the text.
Again, it's encyclopedic so you might find yourself skipping through analysis of
certain parameters, but some of them have interesting applications.
I think it's always a good idea to run
some experiments to validate the mathematical results that we've developed.
And it's easy to generate random permutations, so why not do it to just
check that, say, the average number of cycles or the average number 1-cycles in
a random permutation agree with the results predicted by our analysis.
And even for distribution for that exercise we're doing the distribution of
cycle length takes more computer cycles to study cycles,
but it's worthwhile to run experiments to validate these things always.
And again, it is worthwhile to
practice writing up solutions to exercises like this.
So that's permutations.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
