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.

Â