[MUSIC] Hi and welcome back to Introduction to Enumerative Combinatorics. This is lecture six and it is entitled more on formal power series and nonlinear recurrence relations. In our previous lecture, we discussed linear recurrence relations and sequences defined by these relations. And we found that their generating functions are rational, so they're ratios of two polynomials. In this lecture, we will look at a sequence defined by a nonlinear recurrence relation, namely by catalan numbers. And we'll write down the corresponding generating function. But to do this, we'll need more preliminaries on formal power series. So we have introduced the formal power series as, Formal linear combinations of the following form, a0 + a1q + a2q squared + a3q to the third + etc., where as are coefficients, say real numbers. And q is just a symbol, a formal variable, and you're dealing with such expressions just as you're dealing with polynomials. So you can multiply them, you can add them, and you also can take the inverse two formal power series provided that its constant term is non-zero. This we have discussed in our previous lecture. What else can we do with the formal power series? For instance, if we have two formal part series, we can try to take their composition. So suppose we have another series B(q) = b0 + b1q + b2q squared + etc. And you can try to substitute B(q) instead of the variable q in A. So you take A(B(q)). So this is just, a0 + a1B(q)+a2(B(q)) squared + etc. So this is sum, Of the form. An B(q) To the power n, for n greater than or equal to 0. My question is, when does this expression make sense? What do I mean by making sense? I mean, is it possible to compute each coefficient of this series using only finitely many operations with the coefficients an and bn? The answer is that this sometimes is not meaningful if the constant term B(q) is not 0. Let us look at the constant term of this composition. So, Where do we get constants from? So you see that here we have a0. Then from this, the constant term of this sum is a1 times B0. The constant term of this sum is a2 times B0 squared, etc. So the constant term, Of A, Of (B(q)) is, what we expect to get is a0 + a1b0 + a2b0 squared + etc., up to infinity. This means that we cannot compute it using the quantitative number of operations and this sum may be divergent. It is not computed using only finitely many summations and multiplication. It is always computed by finding the many operations only in the case when b naught is equal to 0. So, unless B naught is 0. So if b naught is not equal to 0, this may be not meaningful. And if b naught is equal to 0, well, this is an easy exercise for you to understand that to compute each term of this sum, you need only finitely many operations. So A(B(q)), Is meaningful, Only if, The formal power series B has, No constant term. Okay, here's an example. So notice that A(q) is the geometric progression with the common ratio q. Which is 1/1-q. And B(q) is just q squared. In this case, A(B(q)) = 1 + q squared, instead of each q, we substitute q squared, + q to the fourth + q to the sixth, etc. And this is the geometric progression with a common ratio q squared. We'll need this operation of composition of two power series further, but before we make some use of it, let us define formal derivation and integration on formal power series. [MUSIC]
