Generating Functions for Integer Partitions | Number Theory 30

[00:00:00]this is the 30th video in a series that i'm making to support a course in elementary number theory we just got done talking about the definitions and some basic examples of integer partitions and then we did a brief stint on generating functions and now we're going to push these two ideas together so let's recall some definitions first so a k tuple lambda is called a partition of n and this is the notation if lambda 1 is bigger than or equal to lambda 2 which is all bigger than or equal to lambda k so in other words we have a non-decreasing sequence and then furthermore we have n equals lambda 1 plus dot dot dot up to lambda k also we say that the function a of q is the generating function for the sequence a sub n as n goes from 0 to infinity if a sub q is equal to this power series the sum as n goes from 0 to infinity of a sub n q to the n so somehow we encode this sequence as coefficients of this power series and then next we have this little definition here that was really part of our calculations or examples from before and that is pi sub m of n is equal to the number of partitions of n with parts that are less than or equal to m and now our first big goal here is to find the generating function for these types of partitions so i've called that pi m q i know this is a little bit strange because we're using the same notation for the number of partitions in the generating function but that's actually pretty pretty common here just remember that when we've got a natural number or a non-negative integer in here we mean the number of partitions but when we have a formal variable in here we need we mean the generating function so this is going to be the sum as n goes from 0 to infinity pi m n q to the n so in order to motivate what we'll eventually come up with let's do a couple of basic examples so let's look at m equals 1 first so notice that's going to be the number of partitions of n using only the part 1.

[00:02:15]so notice that 1 is equal to 1. that's the only partition of 1 anyway but it's definitely the only partition of one using only one and then two is equal to one plus one that's the only partition of two using only one three is equal to one plus one plus one and then so on and so forth so n is equal to 1 plus all the way up to 1. so there is exactly one partition of n using parts that are less than or equal to 1 and only in other words using only one as a part so we can encode that as pi 1 n is equal to 1 for all n bigger than or equal to 0. recall that when n is equal to 0 we fix the number of partitions to always be just one so now let's put this together that means pi one of q is equal to one plus one times q to the one plus one times q squared plus one times q cubed and then so on and so forth so all of these coefficients are 1 because the output of this function is always equal to 1. but by the very important sum of geometric series formula we have this is equal to one over one minus q so that's the generating function for partitions of n using only one okay so now let's move on to our second example which you could probably guess is going to be m equals two okay well let's do a couple of examples first so we've got one equals one that's the only partition of one using one or two in other words parts less than or equal to two we have two equals two or one plus one so that's the only partitions of two using two or one and now we can just kind of build from there so three is equal to two plus one which is equal to one plus one plus one four is equal to two plus two which is equal to two plus one plus one which is equal to one plus one plus one plus one so you can see how this might build out and just as like a little example this means that pi 2 1 equals 1 pi 2 2 equals 2 because we've got two partitions pi 2 3 also equals 2 because we've got two partitions pi 2 4 equals 3 because we've got three partitions now i think it's probably possible to write down a closed formula here but remember that's not our goal right now our goal is to find a generating function so let's find that generating function and we'll do it instead of by putting these numbers as coefficients we'll write the exponents using each of those partitions notice that'll count the same way so we have pi two q will be equal to one plus q to the one so that represents the partition of one plus q to the two plus q to the one plus one so that represents the partition of two so notice there's two there's one plus one or q to the two plus one plus q to the one plus one plus one so those represent the two partitions of three and then so on and so forth so i'll write for four as well so two plus two q to the two plus one plus one q to the one plus one plus one plus one and then so on and so forth so notice we're counting those partitions by just putting in the exponents and now we're going to factor this carefully so let's group all of the terms that do not involve a q squared so that's going to be all of these that i'm underlining in light blue now let's put all of those together so we'll have 1 plus q to the 1 plus q to the 1 plus 1 plus q to the 1 plus 1 plus 1 and then so on and so forth great and next let's group all of the terms that have a q squared so that'll be this one right here let's maybe go ahead and underline this in blue so we can see where it came from so that'll be this right here that'll be this right here and that'll be this one right here but we actually want to skip this one because here we only want to use the exponents of q where we've explicitly written the two one time here we've explicitly written the two two times so let's see what we get here so this would be plus q squared times and now we'll have one plus q to the one plus q to the one plus one plus dot dot dot so let's underline that in red so notice this q squared can be pulled out to give us a one from this term a q to the one from this term and a q to the one plus one from that term okay but now we can really just keep going so the next thing that we'll pull out is all of the instances of q to the two plus two and so we'll have this one and then we'll have q to the two plus two plus one which is further down the line q to the two plus two plus one plus one and so on and so forth so that's going to give us plus q to the two plus two and then one plus q to the one plus q to the one plus one and then so on and so forth and so that goes on forever and then next up we can notice that each of these things which are underlined in these different colors can be summed via the geometric series rule so this guy right here can be summed to 1 over 1 minus q this guy right here can also be summed to 1 minus 1 over q this one right here 1 over 1 minus q and then so on and so forth and now look at the coefficients here we have a coefficient of 1 in front of this 1 over 1 minus q coefficient of q squared here a coefficient of q to the 2 plus 2 which is q to the 4 there the next one will have a coefficient of q to the 2 plus 2 plus 2 and then so on and so forth so let's maybe clean up these observations and then we can write down the generating function in this case so the last board we motivated the ability to write our generating function pi 2q in the following way so we did some intermediate sums of geometric series and then we were left with some coefficients which i've simplified so this is like our one over one minus q so this is only using parts equal to one this is q squared over one minus q so this represents partitions using 1 as many times as we want but 2 only once this right here represents using 2 exactly 2 times but 1 as many times as 1 and so on and so forth but let's notice that this is another geometric series 1 over 1 minus q is the starting term and q squared is the common ratio so we can sum that together to give us 1 over 1 minus q times 1 over 1 minus q squared so that's what we get in the m equals 2 case and i think between this m equals 1 and this m equals 2 case we have a pretty good guess for what it should be in the m equals m case or the general case so let's maybe clean up this we'll state that as a theorem and then move on from there motivated by what we saw in the last board we have the following theorem which explains the generating function for the number of partitions of n whose parts are less than or equal to m so that's pi m q is one over one minus q times one over one minus q squared all the way up to one over one minus q to the m we can write that in product notation as follows so this is the product as j goes from 1 to m of 1 over 1 minus q to the j now we're going to prove this by induction and our base case is actually just done in the examples notice we did two base cases here the m equals one and two base case so now let's make our induction hypothesis so that'll be that we suppose for some k bigger than or equal to 1 we have well this result holds so in other words the number of partitions of n into parts that are less than or equal to k has the following generating function 1 over 1 minus q times 1 over 1 minus q squared ending at 1 over 1 minus q to the k but we could rewrite that with product notation as the product as j goes from 1 to k of 1 over 1 minus q to the j and now we're going to make the following observation as to how partitions of n might split up so let's look at partitions of n with parts less than or equal to k plus one so that'll be the next case in other words the case after the induction hypothesis and these partitions naturally split up into a bunch of parts and what are those bunch of parts well we could first look at partitions with all the parts less than or equal to k so in other words we're using zero parts that are equal to k plus one and then we could build it up from there so next it might be obvious to look at partitions with exactly one k plus one and then all the rest of them less than or equal to k so that would be like the next type of partitions of this type and then maybe just to write one more out this could split up into partitions with exactly two parts that are equal to k plus one and the rest are less than or equal to k okay nice so now let's look at this and notice that these sets over here are disjoint you cannot simultaneously be a partition using zero parts that are equal to k plus one and be a partition using one part equal to k plus one and then so on and so forth and this kind of obviously extends down for all possible values of k plus one in other words using three exactly three terms that are k plus one four terms that are k plus one and so on and so forth so that's going to build the following recursion so how many of these guys are there well there are exactly k pi k plus one of n of these guys then how many are there of this type well there are exactly pi k plus one n of that type then how many of this type well we've used one k plus one so this is in fact pi k n minus k minus one because after using a single k plus one we only need the rest of the terms to add up to n minus k plus one and then so on and so forth down here so this is pi k n minus 2 k minus 2 and then so on and so forth eventually you're going to hit 0 because you'll kind of outstrip the size of n but after that point you can just set all of these things equal to zero okay so now thinking about this we can write down the generating function pretty easily so let's do that on the next board so after our exploration on the last board we're ready to write down the generating function for partitions of n into parts that are less than or equal to k plus 1 in other words the generating function pi k plus 1 q so let's recall how we built this so this was built from partitions that are using zero parts that are equal to k plus one so that would be like pi k q we're using zero parts that are equal to k plus one and then next we would have q to the k plus one pi k q so this would represent using a single part which is equal to k plus one and then everything else is less than or equal to k and then next would be q to the 2k plus 2 pi k q so this would represent using exactly two parts that are equal to k plus 1 and all of the rest of them less than or equal to k and then this extends forever so let's look at what we've got here we've got another geometric series notice our starting term is pi k q and our common ratio is q to the k plus 1.

[00:15:12]so that means this sums up to pi k q over 1 minus q to the k plus 1 just by the geometric series summing formula but now using our induction hypothesis we see that this is exactly one minus q times one minus q squared all the way up to one minus q to the k times one minus q to the k plus one which is exactly what we need it to be to finish off this inductive argument so now that we've got this let's present a quick corollary of this theorem which looks at unrestricted partitions so using the generating function that we developed on the last board let's prove the following correlator which is really important so this is the generating function for unrestricted partitions so that means we have no restriction on the size of the parts and also we have no restriction on the number of parts of a certain size but we didn't talk about that as having to do with this guy up here so notice this has largest part m so if we want no largest part like we do here well we could just take the limit of this guy as m goes to infinity so let's do that so we have p of q is equal to the limit as m goes to infinity of pi m q but notice that's equal to the limit as m goes to infinity of this product as j goes from 1 to m of 1 over 1 minus q to the j but that's exactly equal to this product as j goes from 1 to infinity of 1 over 1 minus q to the j which is the generating function that we're going for so sometimes when doing calculations instead of writing it out in this product notation we'll actually write the terms out because it'll be clear how we're doing the calculations so we would write 1 over 1 minus q times 1 over 1 minus q squared and then so on and so forth including enough terms so that it's clear how we are manipulating those terms so now that we've got this nice generating function for unrestricted partitions let's see the big idea behind this generating function so on the last board we determined that the generating function for unrestricted partitions was this infinite product but i want to recall that each of these rational functions here is really representing this power series like this so notice this 1 over 1 minus q is 1 plus q plus q squared which is one plus one thinking about these as encoding partitions of a certain type the same thing here this is encoding the parts of the partition that are equal to two and so on and so forth so let's maybe see what each part of this product corresponds to so if we were to group all of this together which is the same thing as looking at this entire rational function up here these two guys correspond to parts of the partition equal to 2.

[00:18:20]okay so that's what that means and if we sum it together that's what this rational function up here means but what do the individual terms mean so this individual term right here corresponds to using exactly two parts equal to one because we've got one plus one now that's not really represented up here in the rational function very well that's represented in this expansion and then you could see this more generally over here so this term right here which is q to the m plus m plus m that corresponds to using m exactly three times in the partition so if you've got a feel for exactly how these portions of the generating function build up our counting for the number of partitions you can actually use this to write down generating functions for restricted partitions pretty easily that's exactly what we'll do on the next board now that we hopefully have a good idea for how the parts of our generating function build our counting structure for number of partitions let's do a couple of examples so this first example is all partitions using only parts that are 3 mod 4. so let's look at some examples of this rule for real quick so we've got 3 which is equal to three okay so that's the only partition of three using parts that are congruent to three mod four let's see there are no ways to do four or five using only parts that are through mod four but we can do six six is equal to three plus three we can also do seven which is equal to seven next we could do nine as three plus three plus three so the first several numbers that can be written with parts that are three mod four only have one partition each maybe do a couple of more examples as your warm up to find which is the first number that exhibits two partitions where you're only using parts that are three mod four okay but hopefully by what we saw on the last board we can just write down the generating function for this so the first part of that generating function will be one over one minus q cubed so that's using parts equal to three the next one will be one over one minus q to the seven so that'll be using parts equal to seven the next one will be one over one minus q to the 11 that'll be parts equal to 11 and so on and so forth so we can put this all together and have the product as m goes from 0 up to infinity of 1 over 1 minus q to the 4m plus 3.

[00:21:16]so that's our generating function for partitions who were only using the parts that are congruent to 3 mod 4.

[00:21:24]okay so now let's look at this next example distinct parts so that means we're only allowed to use each part one time or more like generally or with an eye to more generality we're allowed to use each part exactly once or zero times okay so notice one plus q is the portion of the generating function which is using one zero times that would be this one or one one time that would be this q multiply that by one plus q squared that would represent using two one time or zero times one plus q cubed that would represent using three zero times or one time and then so on and so forth so this is going to be an infinite product so we could write this as the product as m goes from 1 up to infinity of 1 plus q to the m so that's another important generating function for partitions into distinct parts so for instance we're not allowed to use one more than once or two more than once so on and so forth now let's look at this funny one which is odd parts used at most twice but no restriction on even parts so we'll have to do this a little bit at a time so that means we can use one at most twice that means we can use it zero times one time or two times so zero times would be a one one time would be q two times would be q squared or really q to the one plus one if you want to think about it like that so these are our parts equal to one no restriction on even parts that means we can use two as many times as we want so that'll be 1 over 1 minus q squared because really we would have the power series 1 plus q squared plus q to the 4th plus q to the 6th forever but that sums to the following rational function okay so now we're on to parts that are equal to three but we're only able to use those zero one or two times so that's going to be one plus q cubed plus q to the sixth then we're on to parts that are equal to four we're allowed to use those as many times as we want so those sum to the geometric series one over one minus q to the fourth but now this extends forever so we're only able to use the odd parts zero one or two times but the even parts are unrestricted so we can maybe put all of this together into the product as m goes from one up to infinity of one plus q to the 2m minus 1 plus q to the 4m minus 2 over 1 minus q to the 2 m i think that would maybe be a good description of this generating function so notice that numerator is talking about how many times we can use the odd parts this would be using 2 m minus 1 0 times 2 m minus 1 1 time 2 m minus 1 2 times but then down here we've got no restriction on the number of even parts okay good so let's maybe get rid of this and we'll do our first theorem using these generating functions so we're going to finish this video off with a theorem and this is maybe the simplest theorem that you can prove with generating functions and that is the number of partitions of n into odd parts which we will denote by p odd n is equal to the number of partitions of n in two distinct parts which we'll denote by p distinct n then i've written that over here so p odd n equals p distinct n for all n okay so let's get to it so let's notice that the sum as n goes from 0 to infinity of p distinct in q to the n so that's the power series that is the generating function for partitions of n into distinct parts we could write that as p distinct q just using our standard notation from before but we know what that is from a previous example so that's equal to 1 plus q times 1 plus q squared times 1 plus q cubed and then so on and so forth so i've left a little gap in there because i'm going to multiply each of these by a special version of the number one so let's insert a one here in the form one minus q over one minus q we'll insert a one here one minus q squared over one minus q squared we'll insert one here one minus q cubed over one minus q cubed and then so on and so forth that's going to extend forever so now let's multiply these together so notice we have a nice product that looks like a difference of squares if we look at each of these pairs like this and then in the denominator we've got the product of all of these 1 minus q type terms so that's going to give us 1 minus q squared from this first blue square 1 minus q to the 4th from the second blue square 1 minus q to the 6th from the 3rd and then so on and so forth so it looks like the numerator looks like the product of all of these even things and then like i said the denominator will be the product of all of them so 1 minus q cubed 1 minus q to the 4th and then so on and so forth but now let's notice that a bunch of stuff cancels so notice this 1 minus q squared cancels with this 1 minus q squared this 1 minus q to the 4th with this one minus q to the 4th this one minus q to the sixth will cancel with a one minus q to the sixth down there and then we're left with one minus q one minus q cubed and so on and so forth in the denominator so let's clean up what we get after all of the cancellation okay so after all the cancellation we're left with the following rational function so it's 1 over 1 minus q 1 minus q cubed 1 minus q to the 5th and then that extends forever so let's notice this controls the number of parts equal to one there's no restriction on the number of number of parts equal to one these are the number of parts equal to three these are the number of parts equal to five and then that extends but there's no restriction on the number of times we can use any of these parts so it's pretty clear that this is the generating function for the number of partitions of n into odd parts which we might denote as p odd q but then that's going to be equal to the sum as n goes from 0 up to infinity of p odd n q to the n so we have the equality of these two power series but that means we have the equality of every coefficient of these two power series but that's exactly what we wanted to show okay so i'll leave you guys with a couple of warm-up exercises okay here are a couple of warm-up problems that are built off of what we just looked at so let's try to write the generating function for these types of restricted partitions so the first is partitions of n into parts that are congruent to 1 or 4 mod 5. this is actually interestingly related to the rogers or monash identities so i'll let you guys look those up if you're interested next is this kind of kooky one that i came up with but i think it's maybe a good exercise to get to to come to grips with how to write generating functions so this is partitions of n using even parts an even number of times with no restriction on the odd parts so that means we're allowed to use 2 0 times 2 times 4 times 6 times so on and so forth we're allowed to use 8 an even number of times as well so that would be 0 times 2 times 4 times and then so on and so forth but like i said we can use the odd numbers as many or as few times as we want okay that's a good place to stop