[SOUND] [MUSIC] So our next goal will be to compute the generating function, p of q. Which is the sum of p(n) times q to the power n = 1 + q + 2q squared + 3q cubed + etc. But, before we do that, let us introduce one more notation. Let p(n,k) denote the number of partitions over the number n into summands not exceeding k. K is greater than or equal to all lambdas. Okay, and let us introduce the generating function for this sequence. So Pk of q. We will denote the sum of p(n,k) times q to the power n, where n is greater than or equal to 0 and k is fixed. We'll also compute this function as well. So, let us consider this simple situation, what happens for k = 1? So. This is ridiculously simple problem. So P and k, p(n,1) is the number of the compositions of n into sums equal to one. And there is only one such decomposition for each n, right? So n is just one plus one plus one, etc. The generating function will be P1(q), and this will be one + q + q squared + q to the third, etc. And this is just the genitive series with the correlation q. And there is a well known formula for this geometric series. This is equal to 1 over 1- q. Okay. So here's the generating function for capital P1 of q. Okay, what happens for bigger case, say, for k = 2. So how many ways are there to represent n as a sum of 2s and 1s? First, let us modify our question. What happens if we only allow sums of which are equal to 2? How many ways are there to represent a number as a sum of 2s? The answer is 0 if n is odd and just 1 if n is even. Okay, so if we represent a number as a sum of just 2s. It is represented in a unique way if the number is even and it can't be represented at all if the number is odd. So the corresponding generating function looks like 1 + q squared + q to the power 4 + etc. So the coefficient in front of each term where then even power of q is equal to 1 and in front of each odd power of q is equal to 0. So this is also a geometric series, and the common ratio is q squared. So the sum is 1 over 1- q squared. So what about P2 of q? It turns out that the generating function for representing a number as a sum of twos and ones is nothing but the product of this series and the series with the common ratio of q. So here is the proposition, P2(q) = 1 + q + q squared + etc) times (1 + q squared + q to the fourth + etc), and using this tentative formula, we get 1 over (1- q) times (1- q squared). Okay. Let's show this. We need to show that the coefficient in the expansion of this product in front of q to the power n is equal to the number of partitions of n into sum of twos and ones. So the coefficient in front of q to the power n in the right hand side is nothing but p(n,2). Okay, indeed. Let's show this. Let's check the right hand side. (1+q+q squared + etc) times (1 + q squared + q to the fourth + etc). Let me write it with a different color, and let me take the product of these two factors. So I will get, expanding this I get 1 times 1, 1 from the first pattern times 1 from the second 1 + q times 1 + q squared times 1 + 1 times q squared from the second factor + q times q squared. + q cubed from the first factor times 1 from the second one + etc. So each summoned in this expansion will have the form q to the power k times for first factor, times q to the power 2L. From the second one. Where k +2L = n. Okay, and we see that this summons by checking it correspond to decompositions of n into sums of 2s and 1s. Namely, for such a summon, we can take the presentation of n and the sum of k1s and l2s. Okay, so we have shown that the coefficient in front of q to the power n is equal to the number of presentations of n as a sum of 1s and 2s. So it is equal to p(n,2). So we have seen that P2(q) is represented as the product of two geometric series. In exactly the same way, we can show that Pk(q) can be represented as the product of k geometric series, namely as follows. Proposition. Pk(q) = 1 + q + q squared + etc. This is the geometric series with the common ratio q times 1 q squared + q to the fourth + etc. The geometric series with the common ratio q squared times etc, times 1 + q to the k + q to the power of 2k + etc. And using the formula for the sum of a geometric series we get that this thing is 1 over (1- q) times (1- q squared) times etc, times (1- q to the k). Or we can use the product sign. This is the product of 1 over (1- q to the j) where j goes from 1 to k. The proof of this proposition is absolutely analogous to the proof of the previous one. Okay and what about P(q)? What about for the generating functions for the number of partitions without any restrictions on the length of the rows? So in fact in this formula, we can take k equal to infinity, and take the product of infinitely many such geometric series. And we get a theorem due to the Leonhard Euler. Which says that the generating function for the number of partitions, P(q), which is by definition, the sum of p(n) times q to the power n. For n greater than or equal to zero is nothing but the infinite product of the factor is 1 over (1- q to the j), where j goes from 1 to infinity. Note that this is an infinite product, but to compute every given coefficient of this product, we need to use only finitely many operations. So say if you want to compute the coefficient in front of q to the power, say, 1000, you only care about the first 1000 factors in this infinite product, because the subsequent ones do not have any qs in the power less than or equal to 1000. Okay, that we have obtained the formula for the generating function of the for partitions. Without any restrictions. And for partitions with the restriction on the length of rows. [MUSIC]