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.
