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.