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.

Â