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. so let's just look at an application of this of say how many unordered trees are there with N nodes? So that's when we say well, we don't consider trees that look the same if you switch the order different. so there's only four of them with four nodes. and for five nodes, there's only nine, because we just write down the first one of each type. every one of those has two singleton, and singleton three belows so they're all the same. If we can switch, order of nodes, and get the same tree, we consider them to be the same. so this one's the same as that and that one's the same as that and so forth. So there's only nine of those but in terms of the combinatorial operations class of all unordered trees, it's just simply H, a tree is a node in a multi-set of trees. and so the construction, immediately gives us the OGF equation. Now this is a complicated OGF equation but, with, the symbolic method we are immediately led to it. and then we can talk later about how to extract coefficients from such and equation. So that's an introduction to power sets and multi-sets and next we'll take a look at different types of combinatorial objects using these operations. [BLANK_AUDIO]