0:03

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

Â 3:05

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.

Â