0:00

Now we're going to look at combinatorial constructions where we talk about taking

subsets of objects in combinatorial classes to build up new classes.

this is, these constructions are more complicated, we didn't cover them in part

one. And this is an example where in the

lectures we'll work at a level in between what we did at part one, and what's in

the purple book where these theorems are just stated and proven in a few lines.

So we're going to look at two additional constructs.

If we have a class of unlabeled objects with their generating function A of z.

Then we're going to look at two operations, the powerset operation and

the multiset operation. Powerset is of A is the finite set of

objects from A without repetition in the multiset of A is the finite sets of

object in A with repetition. and then we'll talk about what the

generating functions of these things are after I show examples.

so powersets. It's the class of all subsets of A.

so these are examples when A is simply one atom, or two atoms, or three atoms,

or four atoms. for example, if I have all the sets of 3

atoms and I wanted all the subsets of 4 atoms.

I just take the ones that don't have the fourth one.

and I take that same list and I add the fourth one to it.

That gives all the subsets of fourth, 4 atoms.

And you've seen this in many different guises before, but not very clear that

The number of elements in a power set of n items is 2 to the n because each time

we're just multiplying by 2. So or just formally that we can use later

on to prove about the generating functions.

if you wanted the power set of m items. You take the power set of m minus 1 items

and you take the Cartesian product of that with the empty set plus the mth

item. That's what we're doing here.

Take the empty set or add the mth item, and that's a limb of how we construct

power sets. so let's look at the generating function.

So if we want the power set class for m atoms that just means pick some out with

no repetitions and so there's a bunch of atoms, each have the generating function

z. the generating function for that is sum

of every object in the class z to the size of that object, the number of items

in the subset or if we use the fundamental identity and collect the 1s

of size n. Then that's also equal to sum m greater

than or equal to zero PMNZ to the n where PMN's the number of subsets of size n for

the m atoms. And again this is very familiar but let's

look how it works formally with the symbolic method.

so the lemma that I just showed is the construction so it's simply the empty set

plus a1 times the empty set plus a2, and so forth, times the empty set plus aM.

and so that immediately translates to the generating function equation, since the

generating function, each one of these is 1 plus z, and there's M of them.

That immediately gives the OGF equation, PM is equal to 1 plus z to the M or

expansion number of subsets of size N. M items is M choose N, which is familiar

in elementary. So that's power sets and and yeah, if you

take PM of 1. That's the total number of subsets of M

of M atoms. That's something on N of P of M and

that's just 2 to the M. So again that's going to confirm

elementary combinatorics. So multiset is the same thing except we

allow repetitions. So the multiset of this single atom is

just a sequence of those. A multiset of two atoms is, for each one

of those you can add one b or two b's or any number of b's, and so forth if

repetitions are allowed. Or again if we want the multiset of m

atoms, you take the multiset of m minus 1 of M and then a sequence of the last one.

the sequence would be 0,1 or are remaining.

So that's the construction for a multiset, now we can do the same thing.

with the symbolic method uh,[COUGH] the with the generating functions and it's

going to be SMN number of subsets of size N with repetitions allowed and the

construction is just sequences across of sequences of each one of them and what's

the sequence of an atom? The generating function for the sequence

of an atom is 1 over 1 minus z. so we get 1 over 1 minus z to the n.

the number of atoms subsets of size n. is that's in elementary generating

function expansion is just N plus N minus 1 choose N minus 1.

And again you may be familiar with that from elementary combinatorials.

So, now we don't have to do that with atoms.

We can do that with any class of unlabeled objects.

So if you have a class of unlabeled objects with an ordinary generating

function of A to z And you take the power set of that class, then the generating

function of, of, of the class that's formed in that way is given by this

equation. there's two different ways to represent

it. I will look at the proof of that in the

next slide. Either it's the product for n bigger than

1 or 1 plus z to the n to the Anth power, where An is the number of objects of size

n in the original class. or it's exponential e to the minus sum k

greater or equal to 1, minus 1 to the k A z to the k over k.

Now, we'll look at the proof of that which is not difficult on the next slide.

And, similarly, for multiset we have a similar equation which is 1 over 1 minus

z to the n to the An which Is e to that power.

so we're going to prove this once. But once it's proved, we can apply it in

the same way as the other operations that we've done for the symbolic method.

these are just quite a bit more complicated in terms of the formula.

So lets look at the proof for our powersets.

so again the powerset of class that consist of 2 atoms is just broken out

either empty plus the one or empty plus the other.

so another way to write that 1 plus z to the, the OGF that corresponds to that is

1 plus z to the size of a, and 1 plus z to the size of b.

so this is when b's are, are atoms that have whatever size.

so a power set of combinatorial class, then just extending that is the product

for all objects in the class of empty plus the object.

and so the generating function is going to translate immediately to 1 plus z to

the side of the object. And just as in the fundamental identity,

if we collect all the objects that have the same size, there's a sub n of them,

and if we sum by n then it's 1 plus z to the n and it's a product and there's a

sub n of them, so it's that to the a A sub Nth power.

That's the generating function for the powerset.

That was the first expression that we gave in the table, or just using exp log

you can write that expression, product of 1 plus Z to the N all to the A Nth power

as e to the quantity Sum integrated equivalent of zero[UNKNOWN] natural log

of one plus z to the n. And now if we expand natural log of one

plus z to the n just Taylor's theorem, thats minus one to the k z to the n k

over k. minus so E to all that power.

Now we can switch order of summation. If we switch order of summation, we have

a sum on K. Inside, we have sum AN Z, Z, Z to the K

to the N and that's the same as A of Z to the K.

over k times minus 1 to the k. So that's just switching order of

summation. Some a n z to the n to the kth power, a

of z to the k. and so that's a of z minus e z squared

over 2 plus a z cubed over 3 and so forth.

Just using x law. so that's a proof of correspondence for

power sets. so we could do the same thing for

multisets. Again, if we have just two objects it's a

product of sequences, so the generating function is 1 over 1 minus z to the size

of the first 1 over 1 minus z to the size of the second.

and if we've got a class of objects... Then it's a product of sequences of all

objects in the class. so that's just the product of 1 over 1

minus the to the size of the object. And again, if we collect on N, then and

bring all the terms of size N together, there's A to the N of them, so we get the

product N bigger than zero[UNKNOWN] quantity to the AN power.

So, that's again, the first way to express the generating function for that

multi-set class. Or again, we can do an X log version

where we write it as E to the sum of AN log 1 over 1 minus Z to the N which is a

double sum if we expand the log but then if we switch or, order of summation then

we get E to the sum K bigger 1 A of Z to the k over k.

so that's the proof of correspondences for multi-sets.

so and again, that's easily just writing that sum out.