0:03

I just want to briefly mention that ordinary generating functions are no the

only way to represent a sequence with a simple function and actually there's an

important one that plays a very important role in analytic combinatorics that I

just want to mention briefly now. you can define other types of kernels to

represent the sequence so instead of Z to the K say we put Z to the K over K

factorial. if we do that then what we have is what's

called an exponential generating function.

so for example the sequence of all 1s, the exponential generating function that

represents that sequence is Z to the N over N factorial and we saw that's E to

the Z and the powers of two again just do the math, two to the N, Z to the N over N

factorial, that's two to the Z to the N over N factorial.

That's E to the 2Z. So same sequence different functions for

representing them in there are situations where it's more natural, it's better,

it's more convenient to use exponential generating functions.

And many other possibilities have been studied.

but for analytic combinatorics we're going to focus on ordinary generating

functions and exponential generating functions.

So it's worth spending here's another one oh, N factorial

itself, the exponential generating function for N factorial is one over one

minus Z. so that's an example of when we might

need it. If you've got a very

a sequence that grows very fast like n factorial ordinary generating function's

not going to work. Some of N factorial Z to the N doesn't

converge for any Z and it's cumbersome to work with so use the exponential

generating function that's one over one minus Z.

It can be a bit confusing because the same functions arise in different

contexts but really not. It's just a different way to represent

the sequence. and we have the same kinds of operations,

and you can read in the book about differentiating, integrating, and so

forth. and there's one important operation

that's what happens when you multiply two EGFs.

Then you get what's called a binomial convolution.

and that's just applying the same steps that we use when we were proving what

happens with the product of two ordinary generating functions but we carry through

the K factorial and the N factorial, so I distribute now when we change N to N

minus K, we've got a K factorial, N minus K factorial but then we can, we need the,

an N factorial in the denominator anyway, so we multiply and divide by N factorial

and now we've got. a exponential after we switch orders.

we've got a exponential generating function for this convolved sequence, the

binomial convolution. And actually there's plenty of

applications where these kinds of sequences arise and we'll see them very

soon. so there's recurrences say, related to

such problems that arise and if confronted with a recurrence like that

we'll have to now naturally from the problem.

It, that one looks like I should use an exponential generating function on.

so this is an example that actually we'll come up with some similar examples in

specific applications related to important algorithms later on.

so FN equals sum NK of N choose K. Fk over two to the K.

how are we going to function find an equation for that number?

well Exponential generating functions we'll

use the same rule except we make an exponential generating function, so that

is multiplied by z to the n over n factorial and sum on n.

Then on the left hand side we get F of Z. And on the right hand side we get a

double sum. and then what we're going to wind up

doing is, kind of, working backwards for the convolution, that we just did.

so, switch order summation on that. that's just switching the sums and,

keeping. Now, if it's all K, then, N's got to be

bigger than K. and then, change N to N + K.

so that brings us N + K in the top of the binomial coefficient, and the exponent is

Z. and N + K factorial.

and then do some, if the N plus K factorials cancel out.

we still have the F K the Z to the K, and the two to the K absorbed together in the

Z to the N and now those are independent sums m so that's the binomial convalution

backwards and so what it says is that F of Z equals E to the Z.

that's Z to the N over N factorial sum and the other one is F to Z over two.

so f of z equals e to the z, f of z over two.

And that's something we can telescope. and this is a little bit formal it's not

necessarily true that it converges but let's [COUGH] not worry about that just

now and work with the idea that we've shown that F of Z equals E of two to the

Z, E to the 2Z. And what's that what's E to the 2Z, the

exponential generating function for? that was one of the first examples that

we looked at. It just says that FN equals two to the N.

in this case, whether or not a generating function converges, we've got an answer

that we can check. 2 to the N definitely equals sum on K N

choose K, 2 to the k / 2 to the k, that's the binomial theorum.

so it looks like a difficult recurrence. it actually has an easy solution with

exponential generating functions. And so N works for similar functions too

where, and that's what happens in the practical applications.

maybe it's N - 1k or maybe there's an extra term of some kind how the same

process works to actually tell us the facts that we need to know about the

algorithms that we're studying. we'll see, in much more context, the

important role that exponential generating functions take, when we look

into, analytic combinatorics in a couple of lectures.

but even in the context of just solving recurrences.

[COUGH], they can be important, as this example illustrates.