PROFESSOR: The final general counting rules that we'll examine is called inclusion-exclusion, and it is a straightforward generalization of the sum rule-- at least in the simple case of two sets that we'll look at first.
So we're going to look at 6042 example of applying inclusion-exclusion, but let's begin by stating what it is.
So the sum of the rule says that if you have two sets A and B that are disjoint-- no overlap between A and B-- then the size of A union B is equal to the size of A plus the size of the B. Well that's obvious. We took that as kind of basic axiom.
But what if they're not disjoint? Suppose that A and B overlap, and there's some stuff in here that's the intersection of A and B where there are points in common, what then is the size of A union B in terms of simpler things that we can count? And the answer is that the size of A union B is the size of A plus the size of B minus the size of A intersection B.
Now, the intuitive reason for that-- and it's not really very hard to make a precise argument-- is that when you're adding up the elements in A, you're counting all the elements of the intersection once. And then when you add in the elements in B here-- A plus B-- you're counting all the elements in the intersection a second time. The ones that are in A minus B get counted once. The ones that are in B minus A get counted once, but the ones that are in A intersection B get counted twice.
So to get the right count, I have to subtract the size of A minus B so it's only counted once in the total formula, and that's an intuitive explanation of why inclusion-exclusion formula holds for two sets.
Let's apply it.
And I'm going to look at an example where we're looking at digit permutations, and I'm going to look at permutations of the 10 digits, 0 through 9 inclusive. There's a standard one where they're listed in order, and there is just a random seeming permutation of the digits 0 through 9. Notice that the 1 and 3-- the 2 is sort of out of order. The rest are in order.
Now, what I'm going to be interested in is those permutations where certain patterns appear. So first of all, let's note it that the number of permutations we know how to count-- it's 10 factorial.
I'm interested in how many permutations have a consecutive 6 and 0, a consecutive 0 and 4, or a consecutive 4 and 2. In other words, two of the consecutive numbers that appear in 6042.
Well, the first one does not. There's no 60, 04, or 42 in this list. This one has a 42. So it would count as one of those permutations that has either a 60, a 04, or 42 because it's got the 42.
Here's one where you've got a 2 and a 4, but that's not a 4 and a 2. And in fact, there is no pattern here of 60, 04, 42. So it's not one of the permutations that I'm interested in.
On the other hand, here's one that's doubly good. This is a permutation that has both a 04 in it and a 42 in it. So it would be one of these permutations of the kind that I'm looking for that has at least one of the pattern 60, 04, or 42.
Well, if I let P sub x be the permutations with the sub-sequence x, then what I'm really saying is that this one with a 42 in it is in P 42 because it's got the 42 pattern.
This one with the 04 and a 42 in it is in the P 04 set of permutations with the pattern 04 intersected with the set of patterns that have a 42. So that's what that one illustrates.
So what we're really asking for then is the union of three things-- the union of P 60, P 04, and P 42. How big is the set of sequences that have a 60 union, the set of things that have a 04 union, the set of things that have a 42? And as we saw illustrated in the previous slide, these are not disjoint.
We'll I've been cheating a little because in order to figure out this one, I'm going to need inclusion-exclusion for three sets instead of two, which is slightly more complicated because I have a union of three things that overlap.
And let's look at that. So what does inclusion-exclusion look like for three sets? If I want to know what's the size of A union B union C, here's a Venn diagram that shows a picture of A union B union C with all possible overlaps illustrated there. And the formula turns out to be-- you add up A, B, and C. You add up the size of A, the size of B, and the size of C.
Now that has a consequence that just that sum of A, B, and C is counting this lens shaped region that is the intersection of A and C. It's counting it twice in the A plus C term. It's counting A intersection B twice, and it's counting this lens shape, which is C intersection B twice.
So in order to get the sum right, I'm going to have to subtract one occurrence of A intersection B, one A intersection C, one B intersection C so that those items are only counted once in this sum.
And then in fact, if you look at this region here, of the sort of rounded triangle region-- which is the intersection of A with B and C-- that one is actually getting counted three times. All three circles overlap it. So when I add in A and I add in B and I add in C, every one of those points there is being added three times.
On the other hand, this rounded triangle shape, which is count of three times in the sum A plus B plus C, is being subtracted three times. Because when I look at A intersection B-- this region-- and I subtract it, I'm taking one away from the count on each point there. And likewise with A intersection C, takes one away. And B intersection C takes one away. Leaving the points in the rounded triangle in A intersect B intersection C not counted at all.
So if I'm going to get the total count right so that every point discounted exactly once, I have to add back in the intersection of A and B and C.
So that's an informal explanation of how the inclusion-exclusion formula works for three sets. We'll look at ways to rigorously prove inclusion-exclusion for an arbitrary number of sets shortly but not in this segment.
Let's go on and apply the inclusion-exclusion rule for three sets to the example of digit permutations with the patterns 60, 04, and 42. And the way to remember this is that the intersections of an even number of sets occur negatively, the intersection of an odd number of sets occur positively, and of course, a single set can be thought of just am intersection of one set with itself. So it's also odd and occurs positively.
All right. Well, now we can apply the formula and say that the set of permutations that have a 60, a 04, and a 42 is equal to the sum of the number that have a 60, the number that have a 04, and the number that have a 42 minus the numbers that have two of the patterns minus those that have all three patterns.
At let's count these individual intersections and sets of permutations separately. It turns out that each one is easy to count, which is a typical situation which is why inclusion-exclusion is a valuable principle because this thing that is harder to count can be broken up into counting a bunch of other things-- intersections-- that are often easier to count. And they will be here.
So let's begin by looking at P 60. P 60 is the set of permutations which have a 60 in them. Well, to count them, we can think about it this way. Think of the patterns with a 60 in them as a permutation of nine items-- the digits 1 through 5 and 7 through 9 and the object 60 that you can place anywhere, but it it's got to be lumped together.
So there are really nine possible permutations of these things-- eight of them digits, and one of them is this pair of digits, 60. And the number of those permutations is equal to the number of permutations with the pattern 60. So the answer is there are 9 factorial permutations with the pattern 60.
Same of course, applies to P 04, and P 42. The number of permutations with a given two digit pattern is 9 factorial. OK.
What about P 60 intersection P 42? Well, you can think of this as the same way. You can think of this as saying, OK. I've got an object 60, I've got an object 42, and I've got the remaining digits 1, 3, 7, 8, 9 to permute. And the sequences of 10 digits that contain both a 60 and a 42 correspond exactly to permutations of the digits 1, 3, 5, 7, 8, 9, and the object 42, and the object 60.
Now, there's eight of things. And so the number of permutations of these eight things is 8 factorial, which means the size of P 60 intersection P 42. The number of permutations of 10 digits that have both a 60 and a 42 pattern is 8 factorial.
Now, that's the case of an intersection where these two things don't overlap. Let's look at the case of P 60 intersection P 04. Well, if it's got both a 60 and a 04, it actually is the same as having a 604. So the intersection of P 60 and P 04 is the set of sequences that have the pattern 604.
And I count those in the same way. I say, OK. I've got an object 604 plus the remaining digits-- 1, 2, 3, 5, 7, 8, 9 for a total of eight objects, and the number of permutations of the 10 digits that half the pattern 604 corresponds to the number of permutations of these eight things. Again, 8 factorial.
OK. Finally, how many permutations are there that have all three patterns-- 60, 04, and 42? That of course, is exactly the same as the set of sequences with the single pattern 6042, the four digit pattern.
And again, we count that by saying that it's the number of permutations of the digits other than 6042-- six of them plus the 6042 object. There are seven of these , and so there are 7 factorial permutations that have all three patterns.
So that means that I can go back to my inclusion-exclusion formula for the sequences that have one of the three patterns-- 60, 04, and 42-- and plug them in. So I get 3 9 factorials for the first sum of three terms.
The intersections-- we all figured out each of them were-- I'm sorry it's 8 factorial. So I'm going to subtract 3 times 8 factorial.
And this last term we figured out was 7 factorial.
Well, I can think of 3 times 9 factorial as 9 times 8 times 3 times 7 factorial, and this is 3 times 8 times 7 factorial. And I wind up
[NO AUDIO]
PROFESSOR: 72,720. That's how many permutations of the digits 0 through 9 there are that have one or another of these three patterns. Turns out that's about 27% of the 10 factorial permutations of 0 through 9.
So that's the significance of applying the disjunction of constraints, this union of having either 60, 04, or 42.