Now we're going to look at compositions and partitions which are interesting combinatorial objects that are well studied and well explained by the symbolic method. So a composition is a simple idea, you want to know the number of different ways to express n as the sum of positive integers. So 2 could either be 1 plus 1 or 2, 3 could be 1 plus 1 plus 1, or 1 plus 2, or 2 plus 1, or just 3 and and so forth. There's 8 ways to express 4 as a sum of positive integers, and 16 ways to express 5 as a sum of positive integers. and again it's easy to guess the pattern there's 2 to the n minus 1 ways to express n as a sum of positive integers. and that's easy to see with the symbolic method. we start out by just considering integers as a combinatorial class. So let i be the class of all positive integers. so it's just like unary. so we take an atom and, and we give it size one so that its generating function is z. if we have seven of 'em then we have z to the 7th. So the generating function for the class of integers is for every integer z to the size of that integer or if we collect them by n i sub n z to the n. And what is a positive integer? It's a sequence of at least one atom. and so from the symbolic method, the generating function is z over 1 minus z. so that means that there's one integer for all positive N. and so that seems like a trivial derivation, but again [COUGH] making these kinds of arguments for things that we understand so well lead us immediately to be able to address more complicated problems with the same basic structure. So now if we look at compositions what we can do is essentially think of a number as being divided up into smaller pieces just by putting, if we have 12 dots, we can put bars in with the 12 dots. And where, wherever the bars do, we convert back to unary. So this is one composition, 1 plus 3 plus 1 plus 5 plus 2 equals 12. and if you look at it that way, and again generating function you, in the standard way then a composition is just a sequence of positive integers. so a sequence of positive intergers is a composition. and but, in a grouping by N, we just need to find a coefficient of z to the N. But sequence of positive integers, the generating function is immediately 1 over 1 minus the generating function for integers. And that one's z over 1 minus z, and if you do the math, you get 1 minus z, over 1 minus 2z for the OGF for composition. and then expanding that it's 2 to the n minus 2 to the n minus 1, or 2 to the n minus 1 different compositions. so very straightforward to analyze this combinatorial structure with the symbolic method. you, and you can argue common authority if you want the zen minus 1 spaces between N dots and every one of them could have a bar or not. And so that's why there's 2 V N minus 1 possibilities in terms of number of compositions. now what about partitions, what if we don't care about the order same way as we did for trees? so there's three, partitions of n-integers so we'll take the one that goes in decreasing order. so all of these, 1 plus 1 plus 1 plus 2, 1 plus 2 plus 1 and so forth, they all represent the same partition, we'll keep the one whose parts are not increasing. so anyway, just crossing out the ones that appear more than once there's seven partitions of five elements expressed again as a sum of unordered positive intergers. It's not so obvious what the answer to this one is I think. you know, look at the you're not going to find the 2 to the n minus 1 pattern here. and people studied this, actually, quite a bit. it's a thing known as Ferrer's diagram. Which is a 2D representation of the partition where you just put the parts in order, just turn them on end and make columns out of them. So if you have that partition, eight plus eight and so forth, so that's parts are in decreasing order if you just turn the dots on end, you get this Ferrers diagram for, of the 42 dots and it's non-increasing, so it's a, a staircase down. The question is, how many different diagrams are there? this so the question is how many Ferrers diagrams are there with N dots? And again this seems like a toy combinatorial question but actually it's going to require the symbolic method and also saddle point asymptotics. It's one of the most difficult asymptotic problems we'll run into. and even, even so, not only that there's lots of applications where people want to study these things. Not just analysis of algorithm but of particle physics and its related to [UNKNOWN] and representation theories. So you can find these objects studies in physics journals, not just math and computer science journals. so we can do the symbolic method part right here. so if we're going to study the class of all partitions then the examples that we just showed it's simply the case that a partition is multiset of positive integers. so that means that sin, since there's only one integer of ea, ea, each kind just directly from the transfer theorem that the symbolic method gives us we have that expression for the generating function for the number of partitions. and to find z to the n, and that again is quite a challenge, goes back to Hardy and Ramanujan. and it's asymptotic to e to the pi squared to 2n over 3 over 4n over the square root of 3. and we'll later on touch on that. but for the present context we get right to the problem with this symbolic method. And this is representative of the huge number of problems where again with trees where a express different problems on trees by having different kinds of restrictions on subtrees and for these types of problems you can consider say compositions into m parts were restricted compositions where you don't allow the integers just some subset of the integers the same with partitions. You can do partitions into distinct parts or restricted partitions where you've taken again any subset of the integers. and all different kinds of problems ensue from considering these things. Right down thee OGF for compositions into parts where the integers are all less than or yule to r. And we'll look at a couple of other ones. how many partitions are there into parts that are power of two? well that's answer's an easy one, and we'll see why in just a second. just from the symbolic method it's one plus z times one plus z squared, one plus z to the fourth, and so forth. So we're looking for the coefficient of z to the n in that. Well, if you just multiply the first two terms that's 1 plus z plus z squared plus z cubed. And then if you multiply that term by the z to the 4th, you can see the first four terms come, and then z to the 4th times each one of them carries the series through to seven. and then same for 8, so you can see eventually, you just get sum of 1 plus z and so forth which is 1 over 1 minus z. so it's just a number of ways to represent an integer as a sum of powers of 2. there's only one, that's sometimes called the computer scientist theorem. problems of this type are very well studied. One of the most famous ones is due to Polya. It's how many ways are there to change a dollar. so let's say all you have is quarters, how many ways are there to change the, a dollar. well, so a dollar is, is 100 cents, and the number of ways to represent integer with quarters is the sum of 25 is 1 over 1 minus z to the 25th. So, coefficient is z to the 100th and that is just 1, that's only 1 z to the 100th term. So, the only way to change a dollar with quarters is 1 with four quarters, so that's fine. So what if you have dimes too. Well, turns out there's 3 ways to change dollar with quarters and dimes. so, you can do that by trying to figure out the possibilities or we can do it with generating functions too. so, number of ways to change a dollar with quarters and dimes. Is coefficient z to the 100 and 1 over 1 minus z to the 25th, 1 over 1 minus z to the 10th. That's the number of ways to represent an integer as the sum of 25s and 10s. so if you multiply out those power series then and look for coefficients of z to the 100. well, you're going to see there's going to be the 1 times a z to the 100th out here. there'll be 2 z to the fiftieths multiplied together. And then there'll be a z to the one hundredth in this one times that one, so there's 3 different things. in face what you can do is just throw out the irrelevant terms if you're just looking for the coefficient of z to the one hundredth. and then you get the 3 different ways. That's how many different ways to change a dollar with quarters and dimes, either four quarters, two quarters and five dimes or ten dimes. so now what if we so that's quarters, quarters and dimes what about if we add nickels? Well now if we add nickels you're going to say well, I, I want a computer to do the symbolic analysis. Or what about pennies? So how many different ways are there to change a dollar with quarters times nickels and pennies. and so Polia had a key insight and wrote a paper on this that shows that it's not difficult to calculate this for small values by hand. Ant it's worth looking at 'cause it illustrates a general phenomenon that very often, one thing that we can do with generated functions is use them to get recurrences and then we can compute with the recurrences to at least a known numerical value some of the things that were studied. So what Polya pointed out was that if you have generating function b of z is equal to another generating function a of z times 1 over 1 minus z to the m. Then you multiply both sides by 1 minus z to the m. and you get this following recurrent. That b sub n equals b sub n minus m plus a sub n. So that gives a way to go a head compute the small values. So, for this example we're going to add the nickels and then the dimes and then the quarters. Actually you can do this in other orders too. So, add, and we're only doing, since everything's a multiple of 5. we'll only look at the coefficients of Z to the power that's a multiple of [INAUDIBLE] , so if we want to compute B sub n so we're going to compute B sub 5 then we take A sub 5 and add B sub 0 to it. if we want to compute B sub 10 then we take A sub 10 and add B sub 5 to it, and so forth. So for this line, its easier to figure out what happens. We just, get[COUGH] N plus 1. so now it starts to get more interesting for the next line. so now, if we want to know. [COUGH] And if we start out with the first two are one, but now if we now want to know b sub 15 then we go ten back so that's a sub 15. that is the line below, plus b sub 5. So that gives 4, and then 2 plus 4 is 6, 4 plus 5 is 9 uh,, 6 plus 6 is 12, 9 plus 7 is 16 and so forth so add each 1 to the 1 2 back so to get this 1 we get 15 plus 49 is 64 and so forth. Now, we can just fill in that whole line in that way and then finally the last line that to get 25, we just go back to 0, and add a sub 25, and then well now we can skip 5 at a time cause our goal is to get to 100. so 49, 72, is 121, and then we have 242 different ways to change a dollar. Well so it's an easy way to do a computation based on a generating function even though computing this in general might be a bit of a challenge for various different types of restrictions and if you want to do an, an exercise start with this table and say the government switches to 20 cent pieces instead of dimes for some reason. How many ways are there to change a dollar and you can run through this computation in the same way in terms of the [UNKNOWN]. So, that's [UNKNOWN] change a dollar problem. That's is an interesting problem in related to compostions and partitions. I'll show you how we can use OGF to address some of these problems.
