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.
Ordinary Generating Functions
Loading...
Do curso por Princeton University
Analysis of Algorithms
32 ratings
Na lição
Generating Functions
Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.
Conheça os instrutores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Today we're going to talk about generating functions.
As you'll see, generating functions are the central object of study in Analytic
combinatorics. But they also have rich history and many
uses and we'll show first how they are used for solving recurrence relations,
and then ease into their use in more general context.
So, to start off, we're going to talk about just what is a generating function.
In this, the fist thing we'll talk about is what is called ordinary generating
functions. So, there's a definition of what is
ordinary generating function? it's a function that's defined as an infinite
sum, involving a free variable, Z in this case over a sequence.
So given a sequence A0, A1, infinite sequence like the types we were working
with recurrences the ordinary generating function of that sequence is obtained by
multiplying the Kth term by Z to the K and then summing over old K.
We also use the notation that inside brackets Z to the N of A of Z, is the
coefficient of Z to the N in A of Z. and a lot of times we want to refer to
what the coefficient is. and we'll see how it, it applies, but
let's just talk formally about some examples of generating functions first.
So for example, if the sequence is all ones, then the generating function for
that sequence is the sum N greater to 0 Z to the N, which is geometric sum 1 / 1 -
Z. or if you have one 1/2. 1/6. 1/24, the
sequence is one over n factorial. The generating function of that sequence
is sum n bigger than zero, z to the n over n factorial, that's e to the z.
So that's examples of generating functions.
And we'd say the coefficient of Z to the N and E to the Z is one over N factorial.
so that's ordinary generating functions. now the significance of defining a
generating function is that it allows us to represent an entire infinite sequence
with a single function. rather than carrying around the infinite
sequence, 1/n factorial, we just work with the single function, e of z.
And that turns out to have all kinds of benefits when we're doing analysis of
algorithms, and studying properties of combinatorial structures.
But before getting into the applications, let's look again at some more basic
operations on generating functions that we'll use in order to be able to, we need
to be able to find the generating function of a given sequence.
And we need to be able to see the sequence back, given the generating
function. Then we use some relatively simple
operations to get these jobs done. So for example, here's the scaling
operation. If you have a of z, tis is just
generating function for some sequence, if you multiply the argument by a constant
c. So, just evaluate a of CZ then just do
the math. That's the sum of c, c to the k, z to the
k. That's the generating function of the
sequence a0, ca1, c^2 a2, c^3 a3, and so forth.
and that's just, from, from the math. CKZK is the
Is the generated function of that sequence.
So here for example, if you have the sequence that's all ones, where it's,
ogf1 over one minus z. then one over one minus 2z is the sum of
two to the n, z to the n, which is the generating function for the powers of
twos. So that's scaling.
So that's an easy way to get generating functions for different sequences out of
a known sequence. and again, we'd say coefficient of z to
the n and 1over one minus 2z is two to the n.
So that's scaling. let's look at another example, addition.
That's an easy operation in generating functions.
If you have two generating functions on two different sequence, then the sum of
the generating functions is the the OGF of the term by term sum of the sequences.
So, for example, these two generating functions that we've developed here if we
subtract the say we subtract the first one from the second,
1u200bz-u200b1/u200b1-u200bz over, 1 - 2Z - 1 / 1 - Z that's the generating
function for powers of 2-1. so with each one of these operations we
enrich the set of sequences that we know generating functions for.
differentiation that's another thing, if we have a generating function A of Z = A
K Z to the K, if we differentiate that. That's Z a prime of Z.
This KAKZ to the K. that's the generating function of this
sequence A1, 2A2, 3A3, and so forth. so, then that's a useful operation, that
we can use again to get, generate functions for more sequences. So for
example with our simple geometric sum for the sequence that's all 1s and
differentiate that. Differentiate the left side it's Z over
one minus Z squared. and the right side tells us that's the
generating function for the natural numbers.
Sequence 0, 1, 2, 3, 4, 5. We can do that again, we can continue
differentiating and get a richer set of functions.
So differentiate again, it's Z squared over one minus ZQ.
and that's the generating function for the binomial coefficients, N choos 2
[COUGH], or N times N - 1 / 2. and actually we can get a generating function
for binomial coefficients on the lower index, by differentiating, N times, in
this way, and you can, check that out. The generating function for N choose M,
is Z to the M, over one minus Z to the M plus one.
and as we saw special number sequences like the binomial coefficients arise when
we're studying algorithms and combinatorial structures.
so with generating functions we can work with all these kinds of sequences with
just one function. so [COUGH] oh, and this is just dividing
by, dividing out z to the n, we get a slightly different look at that same
generating function. and we'll have use for applying all of
these equations which are in tables in the book later on.
okay, we can go the other way and we can
integrate. if you have a OGF if you integrate it
from zero to Z. if you do it term by term the definition,
you see that, that gives us the OGF of the sequence, A1 over two, A2 over three
and so forth. so, taking our standard integrating it.
On the left, it's natural log of one over one minus Z.
On the right, it's the sum Z to the N over N or the generating function for the
sequence, one, one half, one third, one fourth, and so forth.
[COUGH] so that's integration. and we can, actually, integrate more and
get more, answers, but, let's look at another thing,
In that is, partial sum, if you have a genarating function and you multiply by
one minus Z, then you get the generating function of the partial sums of the
sequence. so the original sequence is A0, A1, and
so for, partial sums there A0, plus A1, A0 plus A1, plus A2 and so forth.
Let's look at a proof of that fact so that's just running down the definition
of the two sequences 1 1 1 - z is some big until zk and AFC is by definition
some ingredients of a and zn so we have the product of those two sums.
so we distribute to bring in the powers of z together and give us that double
sum. then the next thing is to, in the inner
sum, change N to N minus K. and so then we have A, N minus K and Z to
the N so, there's only, N in the exponent of Z, and then switch order of summation,
so K be going in your little zero, N bigger than or equal to K, if we switch
order of co, summation that's the same as N bigger than zero, the K restricted to
between, be between zero and N. and then, in that inner sum, we can
change, k to n - k. and then we see that we have the partial
sums. So the generating function.
so this product is the generating function of that sequence which is the
partial sums. so, that's another, fine operation, to be
able to perform to give us a richer set of functions, of sequences that we now
generating functions for. So for example if given our two of the
generating functions that we've already derive two of the sequences that we've
already derived generating functions for. If we multiply those together.
Or one over one minus Z times, log one minus Z, we get the generating function
for the harmonic numbers, a harmonic numbers is sum from, of K goes from one
to N of one over one mine, one over K. and we saw that the harmonic numbers,
arose in the analysis of quick sort and naturally arise in many places in the
analysis of algorithms and now we have, we can represent'em with that single
function, one over one minus Z, natural log of, one over one minus Z.
and that partial sum idea, generalizes to the idea of a convolution.
if you have, any two generating functions, you can multiply them
together. and you get the, generating function for
this, convolved product. sum from where the nth term in the
sequence is sum from zero goes from k to n of akbn-k.
And here's the proof of that. It's just pretty much the same as the
proof that we just did for partial sums where we distribute then we change in the
inner sum. We change n to n - k [COUGH] and then we
switch order of summation and that gives us the convolved product.
So that's convolution. so for example, if, another way to derive
the generating function for the natural numbers, is just to, square the
generating function for ones, and then that, you know you can do the math to see
that this convolved product is just N plus one in that case.
And that's a different way to derive the generating function for the natural
numbers. So that's convolution.
So the summary is that we can, what's called, expanding a generating function
by, the. expressing an unknown generating function
as a power series. That's finding the coefficients.
in, you can look at what we've been doing as both directions given a sequence
what's the generating function or given a generating function what's the sequence.
So let's look at the first one given a, second one given a generating function
what's the sequence what we've really been using is Taylor's theorem.
That if you can differentiate the function then you can expand it and know
the coefficients of Z to the N, it's just the Nth derivative of the function
divided by N factorial. That's really what's behind the series
that I gave for E to the Z, Z to the N over N factorial.
or for one over one minus Z, the geometric series.
the derivatives give factorials and they cancel out and you get one.
So you can get your basic starting point from the Taylor Theorem usually and
that's. that's what I just mentioned.
But also, you can reduce to known generating functions.
as we did for example. if we have 1 / 1 - z.
Natural log of 1 / 1 - z. We know how to find the coefficients of z
to the n in that. by, the process of convolution.
so that's a summary of what we do to find coefficients given a generating function.
And so the other way, if we're given this sequence.
how do we find the generating functions? The same is just the same thought, just
worked the other way. we integrate 1 / 1 - z, to get the
generating function for one over k, and then convolve it with 1- z.
to get our generating function. So that's, working with generating
functions, just using the basic operations, that we've talked about.
So here's a exercise that now you should think about to cement your understanding
of the idea of ordinarity generating functions and the sequences that [COUGH]
the sequences that they represent. So let's prove that using generating
functions, prove that the sum of the harmonic numbers from K goes from 1 to N
has this value. remember when we talked about solving
recurrences we said that we're going to find that we need, we're going to have
sums that we need to evaluate and how are we going to evaluate a sum like that if
it's going to turn up, and generating functions are a reasonable tool for doing
something like this. So think about if you, if you can solve
that problem to apply your understanding of the last couple of slides in the
lecture. So what we do is for the left-hand side,
so what's the generating function for the left-hand side?
Well we know the generating function for the harmonic numbers, that's one over one
minus Z, log of one over one minus Z. If we multiply that by one minus Z, then
we get the generating function for the sum.
So first thing, that gives us the generating function for the left-hand
side. So now to what we want to do is we want
to extract coefficients from that generating function in a different way.
And what we'll do is we'll. convolve natural log of 1-z with 1 / 1 -
z^2 to get the coefficients. So that tells us right away that the
coefficient of z to the n in this its a convolution, its a summon k the
coefficient of z to the n in that one will n - it and the coefficients z the n
and that one over k. So, that's just a convolution of, simple
convolution of those two generating functions.
It's a sum, but it's, all the pieces of that sum we can do.
we just have to do a little bit of math. It's N plus one, times H of N, that's the
first term. And then, minus K over K, and there's N
terms, it's just minus N. And then, just need to note that H of N
is H of N plus one, minus one over N plus one.
And then, a little algebra gives us the solution.
So that's an introduction to ordinary generating functions and some
calculations that gives us the useful ways to work with sequences and evaluate
sums and do other operations just because of the idea that we can represent an
entire sequence with the single mathematical function.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
