[MUSIC] Hi, and welcome back to Introduction to Enumerative Combinatorics. We started the second half of our course, this is lecture five of our eight lecture series. And it is entitled Generating Functions. In this lecture we'll define the notion of generating functions. It is a very convenient way to look at sequences of numbers. So in our previous lectures we were dealing with sequences of various numbers that had some combinatorial nature. They were counting elements in various sets and so on. And while generating functions allow us to look at such sequences as a whole. So here's the definition. Let. A0, a1, a2, etc., be a sequence of numbers. Well let's say that a IR, just real numbers, we don't require them to be integers or whatever. And so this sequence is indexed by non-negative integers, 0, 1, 2, etc. So the generating function of this sequence Is the following formal power series. We denote it by A(q) where q is a formal variable. And this is a0 + a1q + a2q squared +... + anqn +... So while this sequence can be infinite, so this expression is not a polynomial, it is a formal power series. We'll speak about formal power series in a minute. And we can use a shorthand notation, A(q) is the sum of anqn, for n greater than or equal to 0. Okay, so let us first consider some easy examples. Let us start with a not very interesting sequence, which consists of equal numbers of just ones. Examples, Example 1. Suppose that a0, a1, etc., is just the sequence of 1s. In this case the generating function of this formal power series. A(q) is, well let's look at this definition. We need to write down 1+q times 1, this is q + q squared +... + qn. And then up to infinity. So this is just the geometric progression with a common ratio q starting with 1. And we know how to compute the sum of this progression. This is 1 / 1-q. Well, a little bit later we will explain how to understand this equality formally. What does this expression mean? Okay, here's another example, a variation of this one. Example 2, what if we start not with a sequence of 1s, but just with a geometric progression? So, a0, a1, etc., is a geometric progression with the common ratio, let's say lambda, lambda, lambda squared, lambda cubed. In this case, our A(q) will be a geometric progression again, but the common ratio will be equal to lambda times q. So this will be 1 + lambda q + lambda squared times q squared + and so on and so on. And this will be just 1/ 1- lambda, here. So, This expression keeps track of this sequence. So the sequence a0, a1, etc., is just a sequence of coefficients of this expression. Or, if you wish, you can take the series expansion of this guy here. And its coefficients are equal to a0, a1, and a2 and etc. Okay, here's our third example which is somewhat more interesting. Sometimes we're dealing with infinite sequences or sometimes we're dealing with finite ones. So as an example, let's take the mth row of the Pascal Triangle. Let (a0, a1, a2,...am) be mth row of the Pascal triangle. This means that, an is just m choose n. Or you can suppose that this sequence is infinite, so We can think than an = 0 for n greater than m. So, this definition makes sense. Because the number of ways of picking an n element subset of an m element set is equal to 0. If n is greater than m. So, this makes perfect sense. Okay, and in this case, the generating function will be as follows. A(q) for this sequence is, m choose 0 + m choose 1 times q +...+ m choose m times q to the power m. And note that this will be polynomial. There will be no terms with powers of q greater than m. So there will be just m plus 1 terms in this expression. And you know very well that this is, in fact, the following expression. This is (1 + q) to the power m. So this is Newton's binomial theorem. So, Newton's binomial theorem tells us that the generating function for the mth row of the Pascal triangle is nothing but (1 + q) to the power m. [MUSIC]
