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.