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.