In this final piece, we'll discuss the application of the method of generating functions to the combinatorial problem which we are dealing with in our lecture four. Namely to getting an expressed formula for Catan numbers. Let me recall that the Catalan numbers, Were defined by the following recurrence relation. C0 was equal to 1, and Cn was defined by the previous ones as C0 CN minus 1 plus C1Cn minus 2 plus C2Cn minus 3 plus etc plus Cn minus 1 C0. That is sum for i for 1 to n minus 1 of CiCn-i-1. So the first several Catalan numbers were. 1, 1, 2, 5, 14, 42, etc. In the lecture four, we have obtained an explicit formula for Catalan numbers, using some clever combanitorial trick, the reflection method. In this passage, we will see how to avoid this trick from a power series and the expansion for Newton's binomial for a non-integer alpha. Okay, let me take the following thing. Let me first form the generating sequence for Catalan numbers. Generating functions sorry. It is as follows Cat(q) is the sum of Cn q to the power n for n non negative and it is one plus q plus two q squared plus five q to the third plus etc. Okay, and let's see what happens if we take, well this is an infinite series. And what happens if we take this series and multiply it by itself, we'll take it square. Moreover, we multiply it by q. So q times Cat of q squared is C0 squared times q plus C0 C1 + C1 C0 q squared + (C0 2 + C1C1 + C2C0) q to the 3rd + etc. So you see that these qualifications are exactly the Catalan numbers. Number 1, 2, 3, and so on. So, what we'll get will be almost the gyrating function for the Catalan numbers. Cat of q. The only difference is that it won't have any constant term. And in the original function, the constant term was 1. So this is Cat(q)- 1. So we get the following equation. We see that, q times Cat of q squared minus Cat of q plus 1 is equal to 0. This is a quadratic equation. With coefficients from the ring from a power series and the solution of this equation can be also found as a formal power series. Well, we know the general formula how to solve quadratic equations and it tells us that the solution is as follows. This is 1. That is the minus linear term of the equation minus the square root of the discriminant, which is 1 minus 4q divided by q taken twice Okay, why do I take the minus sign here and not the plus? Because This expression in the numerator is a formal power series. In this case is divisible by q and I want to divide it by q because I have q in the denominator. And if I take plus here, what am I going to get will be a power series with a no zero constant term which will not be divisible by 2q. So I need only one solution out of this two solutions of my quadratic equation. And so I have this expression for the generating function of the Catalan numbers and what I'm going to do now is I'm going to use the Newton's binomial theorem to expand this as a formal power series. I need to compute the expansion for the square root of 1- 4q. It is 1- 4q to the power of one half. And this can be computed by Newton's binomial theorem. So this is the sum for n > 0 of one-half choose n times- 4q to the power of n. Let me write it as follows, negative 1 to the power of n times 4 to the power of n times q to the power of n. Let us write down an explicit expression for the binomial coefficient, one-half choose n. It is as follows one-half choose n is 1 over n factorial times one-half times minus one-half then we subtract 1 from 8 from the previous multiple times minus three-halves, and etc. And we have n factors of this type. This means that the last factor will be -2n- 3/2. And this is negative one to the power n minus one divided by two to the power n times n factorial times one times three times etc times 2n minus 3. And let me Write this expression in a slightly different way, namely let me multiply the numerator and the denominator by two, four etc up to to 2n and by 2n-1. The last odd factor which is missing here. So this is -1 to the power n divided by two 2 to the power n times n factorial, times 1 over 2, 4 etc 2n minus 2 times 2n times 1 over 2n minus 1 times 2n factorial. And what is this expression? It is exactly 2 to the power n times n factorial. So we have, of course here it's n minus 1 not n. Minus 1 to the power n minus 1, 4 to the power n times n factorial squared. Times 2n-1 multiplied by 2n factorial. And this is, (-1) to the power n- 1 times 4 to the power n times (2n- 1) times (2 n choose n). And this is the expression which, well something very similar appeared in the explicit formula for Catalan numbers. And of course this is not a coincidence, so having this, we see that this 4 of n and this 4 walks to the power n and this 4 walks to the power n vanishes the minus sign also vanishes. So the square root of one minus 4q is minus the sum of 1 over 2n- 1, Times, 2n choose n times q to the power of n for n greater than or equal to 1. And this is almost what we need. To get the generating function for Catalan numbers, we need to subtract this expression from 1 and divide it by 2q. And in this way, we'll get our final answer, Cn, the nth catalog number, will be equal to one-half, coming from the denominator here times the coefficient in front of q to the power n+1 in this expression. So it will be 1 over 2n plus 1 times 2n plus 2 choose n+1 And this is, well it is easy to understand that this thing will be indeed equal to 1 over n plus 1 multiplied by 2n choose n, or to write it in a slightly different way, this is 2n factorial divided by n factorial times n plus 1 factorial. And this is our explicit formula for Catalan numbers, and we recover it once again from the method of generating functions and in this proof we did not use the combinatorial reflection trick. So the generating functions and formal power series give us a very powerful method of solving various combinatorial problems. Thank you.
