0:04

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?

Â 5:17

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.

Â 12:07

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.

Â