WEBVTT mathematics/probability/murray
00:00:00.000 --> 00:00:05.100
Hello, welcome back to the probability lectures here on www.educator.com, my name is Will Murray.
00:00:05.100 --> 00:00:09.900
Today, we are going to talk about the rule of inclusion and exclusion.
00:00:09.900 --> 00:00:18.300
The rule of inclusion, exclusion is a way of counting the union of two or more events.
00:00:18.300 --> 00:00:21.700
Let me show you what is going on here.
00:00:21.700 --> 00:00:27.200
I'm just going to show you the version of inclusion, exclusion of two events first.
00:00:27.200 --> 00:00:30.400
Then I’m going to show you the merging with three events in a moment.
00:00:30.400 --> 00:00:37.700
The idea here is that you got two events here and I will call them in red and blue circles here.
00:00:37.700 --> 00:00:40.700
We are trying to count the union in there.
00:00:40.700 --> 00:00:43.800
I’m going to call these events A and B.
00:00:43.800 --> 00:00:49.000
I’m trying to account the combined area between A and B.
00:00:49.000 --> 00:00:56.200
The rule of inclusion/exclusion says that if you want to count the union of A and B,
00:00:56.200 --> 00:01:01.800
what you do is you count A separately by itself and then you count B separately by itself.
00:01:01.800 --> 00:01:07.000
If you do that, what you have done is you have counted everything in A.
00:01:07.000 --> 00:01:11.600
You will count all this area right here and then you count everything in B.
00:01:11.600 --> 00:01:15.500
You have counted all this red area right here.
00:01:15.500 --> 00:01:21.300
The problem is that you have over counted the stuff that is common between A and B.
00:01:21.300 --> 00:01:26.500
You have over counted all this stuff in the middle here, the intersection of A and B.
00:01:26.500 --> 00:01:29.100
To fix that, you subtract that off.
00:01:29.100 --> 00:01:32.900
That is where we get this last term in the formula.
00:01:32.900 --> 00:01:36.900
You subtract off the intersection of A and B.
00:01:36.900 --> 00:01:39.800
That is the rule of inclusion/exclusion for two events.
00:01:39.800 --> 00:01:47.200
This is also useful if you solve it the other way around, if you solve for the intersection instead of the union.
00:01:47.200 --> 00:01:52.600
If you just take this same rule and you move the intersections to the other side and
00:01:52.600 --> 00:01:57.200
move the union over to the right hand side, then you get a parallel rule
00:01:57.200 --> 00:02:10.100
which tells us that you can count the intersection of A and B by first counting A + B, and then by subtracting off the union.
00:02:10.100 --> 00:02:16.400
It is basically the same rule but you swap the rules of intersections and unions.
00:02:16.400 --> 00:02:19.600
That is the inclusion/exclusion rule for two events.
00:02:19.600 --> 00:02:24.800
We will see some examples in the problems later on where you get some practice counting those things.
00:02:24.800 --> 00:02:32.000
First, we want to go ahead and look at the inclusion/exclusion rule for three events.
00:02:32.000 --> 00:02:33.800
That one is a little more complicated.
00:02:33.800 --> 00:02:40.800
I will draw more complicated picture here because we are going to have three different events going on.
00:02:40.800 --> 00:02:44.400
We will try to count all three.
00:02:44.400 --> 00:02:53.900
There is my A, there is my B, they have to be the same size which is good because mine are not.
00:02:53.900 --> 00:02:55.900
There is my C.
00:02:55.900 --> 00:02:59.000
We are trying to count the union of the three events.
00:02:59.000 --> 00:03:03.500
We are trying to count the area that is covered by all three circles here.
00:03:03.500 --> 00:03:06.800
First, we count all the area inside A.
00:03:06.800 --> 00:03:11.500
That is all that area right there, all the blue areas.
00:03:11.500 --> 00:03:14.800
That is what is going on here with the A right there.
00:03:14.800 --> 00:03:16.800
Then, we count all the area inside B.
00:03:16.800 --> 00:03:21.100
Let me shade that in red.
00:03:21.100 --> 00:03:25.200
We count all that area right there, that is the B.
00:03:25.200 --> 00:03:31.400
I will color the area for C in green.
00:03:31.400 --> 00:03:36.300
We count all that area in green here.
00:03:36.300 --> 00:03:38.500
That is where that term comes from.
00:03:38.500 --> 00:03:42.000
If you look, we have over counted a lot of the area in here.
00:03:42.000 --> 00:03:45.100
We have counted a lot in this area more than once.
00:03:45.100 --> 00:03:52.000
First of all, we look at the common area between A and B, the intersection of A and B.
00:03:52.000 --> 00:03:55.100
That is A intersect B right there.
00:03:55.100 --> 00:03:57.800
It looks like we counted it twice.
00:03:57.800 --> 00:04:01.100
We counted it once in red and once in green.
00:04:01.100 --> 00:04:02.900
We have to subtract it off.
00:04:02.900 --> 00:04:07.000
I'm going to show you that subtraction term right here.
00:04:07.000 --> 00:04:10.200
That is where we subtract off the intersection of A and B.
00:04:10.200 --> 00:04:20.900
And then A intersect C over here is colored both blue and green, that also got counted twice.
00:04:20.900 --> 00:04:25.200
I will subtract that area off right here A intersect C.
00:04:25.200 --> 00:04:30.700
And then a similar thing happens where B intersects C, is this area right here.
00:04:30.700 --> 00:04:33.600
The red and green areas, that is B intersect C.
00:04:33.600 --> 00:04:38.700
That counted twice so I will subtract that off.
00:04:38.700 --> 00:04:45.900
It gets a little more complicated because there is one area in the middle which I color in yellow.
00:04:45.900 --> 00:04:50.400
This area right here, this area in the middle.
00:04:50.400 --> 00:05:02.900
I will see if I can describe that in yellow.
00:05:02.900 --> 00:05:13.200
That is A intersect B intersect C.
00:05:13.200 --> 00:05:19.500
What happened was that originally got counted 3 separate times and it got counted in A,
00:05:19.500 --> 00:05:22.600
it got counted in B, it got counted in C.
00:05:22.600 --> 00:05:26.100
But then, it got subtracted off three separate times.
00:05:26.100 --> 00:05:29.100
When we subtracted off A intersect B and A intersect C, B intersect C.
00:05:29.100 --> 00:05:36.500
We kind of counted it three times and then we subtracted it off three times.
00:05:36.500 --> 00:05:38.800
The result that it got counted 0 times.
00:05:38.800 --> 00:05:42.700
That area did not get counted at all in the final analysis.
00:05:42.700 --> 00:05:51.000
What we have to do is add that area back in and that is where this final term comes for the inclusion/exclusion formula.
00:05:51.000 --> 00:06:00.500
A intersect B intersect C, we have to add it back in one more time to make sure it is counted exactly once in the final formula.
00:06:00.500 --> 00:06:08.700
Our formula, ultimately, if you want to count A union B union C, what you do is you count A, B, and C separately
00:06:08.700 --> 00:06:15.400
and you subtract off each of their intersections and then you have to add back in the intersection of all three.
00:06:15.400 --> 00:06:22.200
It is a bit complicated, that formula, we will see some practice in the exercises.
00:06:22.200 --> 00:06:25.400
Let us go ahead and try some examples out.
00:06:25.400 --> 00:06:32.300
First example here is, we are at a small college and apparently, there are 150 freshmen here taking English
00:06:32.300 --> 00:06:35.700
and 120 freshmen at this college are taking Math.
00:06:35.700 --> 00:06:42.300
There might be some overlap, in fact it tells us that there are 90 freshmen taking both classes.
00:06:42.300 --> 00:06:46.200
The question is how many are taking at least one of English and Math?
00:06:46.200 --> 00:06:50.900
How many freshmen will there be taking at least one of English and Math?
00:06:50.900 --> 00:06:54.200
To solve this, I'm going to set up some events here.
00:06:54.200 --> 00:06:58.300
I’m going to say A is the freshmen taking English.
00:06:58.300 --> 00:07:01.800
I will just write English for short here.
00:07:01.800 --> 00:07:08.500
B is the freshmen taking Math.
00:07:08.500 --> 00:07:14.700
We want to count how many are taking at least one of the two which is the union of the two sets,
00:07:14.700 --> 00:07:18.300
because it is all the people taking English or Math or both.
00:07:18.300 --> 00:07:25.000
What we want to count here is A union B.
00:07:25.000 --> 00:07:29.900
That is straightforward application of our inclusion/exclusion formula.
00:07:29.900 --> 00:07:31.800
Let me remind you what that was.
00:07:31.800 --> 00:07:36.300
The way you count A union B is you count A and then you count B.
00:07:36.300 --> 00:07:42.900
And now you have over counted the intersection so you want to subtract off the intersection - A intersect B.
00:07:42.900 --> 00:07:46.200
In this case, all the numbers are just given to us right here in the problem.
00:07:46.200 --> 00:07:50.700
The number of people taking English was 150.
00:07:50.700 --> 00:07:55.200
The number of people taking math is 120.
00:07:55.200 --> 00:08:01.300
The number of people taking both of them, that is the intersection is 90.
00:08:01.300 --> 00:08:13.600
We have 270 - 90 and that simplifies down to 180 freshman here are taking either English or Math or both of them.
00:08:13.600 --> 00:08:23.600
The other way to look at this is to draw one of our Venn diagrams and then fill in the numbers on each of these.
00:08:23.600 --> 00:08:25.700
We have a certain number of people taking English.
00:08:25.700 --> 00:08:29.000
A certain number of people taking Math.
00:08:29.000 --> 00:08:33.100
There is English right there and there is Math.
00:08:33.100 --> 00:08:35.100
We have a certain number people taking both of them.
00:08:35.100 --> 00:08:38.400
Let me fill in the people taking both of them first.
00:08:38.400 --> 00:08:42.500
There are 90 people taking both of them.
00:08:42.500 --> 00:08:45.000
There is a 150 taking English.
00:08:45.000 --> 00:08:47.000
We already accounted for many in the overlap.
00:08:47.000 --> 00:08:52.300
There must be 60 more of them just taking English but not Math.
00:08:52.300 --> 00:08:58.700
In math, we got 90 that we already accounted for in the overlap but 120 totals.
00:08:58.700 --> 00:09:02.000
There must be 30 out here just taking Math.
00:09:02.000 --> 00:09:11.400
If you try to figure out how many there are taking either one or both, it would be 60 + 90 + 30.
00:09:11.400 --> 00:09:20.400
And of course that gives you the same number we got as 180 students taking either one.
00:09:20.400 --> 00:09:23.700
Let me recap quickly how we got those answers.
00:09:23.700 --> 00:09:27.400
We set up events for the students taking English and math and then
00:09:27.400 --> 00:09:31.900
we just use our straightforward inclusion/exclusion for two events.
00:09:31.900 --> 00:09:40.200
The number of people in A union B is number in A + number in B - the number in both A and B which is the intersection.
00:09:40.200 --> 00:09:46.000
Those numbers come straight out of the stem of the problem and we add them up and we get 180.
00:09:46.000 --> 00:09:51.700
This was a little pictorial way to illustrate it and figure out directly if we break down
00:09:51.700 --> 00:10:01.500
how many students are taking both, that is 90 taking both and then the 60 really came from doing 150 – 90,
00:10:01.500 --> 00:10:07.900
because there are 150 taking English and we know that 90 of them are already accounted for taking Math.
00:10:07.900 --> 00:10:16.900
This 30, in a similar fashion came from 120 - 90 because there are 120 taking Math
00:10:16.900 --> 00:10:23.500
but we know that we already accounted for 90 of them also taking English.
00:10:23.500 --> 00:10:28.200
That tells us exactly how many students are in each group and we can add those up
00:10:28.200 --> 00:10:31.800
to find the total number of students taking English or Math.
00:10:31.800 --> 00:10:35.700
Now, I want you to hang onto these numbers for the next example because in the next example,
00:10:35.700 --> 00:10:44.700
we are going to stay at the same small college and we still have the same number of people taking English and Math.
00:10:44.700 --> 00:10:47.400
We are going to add in a third subject which is History and
00:10:47.400 --> 00:10:53.300
we are going to have to use our inclusion/exclusion formula for three events.
00:10:53.300 --> 00:11:03.400
We will use the same number so make sure you understand these numbers before you move on to example 2.
00:11:03.400 --> 00:11:07.200
In example 2, we are at the same college that we were in for example 1.
00:11:07.200 --> 00:11:12.600
If you have not just watched the video for example 1, go back and watch that one first because
00:11:12.600 --> 00:11:18.800
I'm going to keep using the same numbers that we figure out for example 1 in example 2, at the same college.
00:11:18.800 --> 00:11:22.500
We are going to use the same events as well.
00:11:22.500 --> 00:11:34.500
A is the event of a student taking English and B is the event of a student taking Math.
00:11:34.500 --> 00:11:41.200
And now we are introducing a third event, C is the event of a student taking history.
00:11:41.200 --> 00:11:48.500
And let us see, we are trying to find out how many are taking at least one of the three?
00:11:48.500 --> 00:11:51.900
That would be the union of our three events.
00:11:51.900 --> 00:11:53.700
We are going to count that.
00:11:53.700 --> 00:11:55.800
We are going to use some of the numbers from example 1.
00:11:55.800 --> 00:11:58.200
Remember to get the numbers from example 1.
00:11:58.200 --> 00:12:03.800
I'm going to write out the formula for inclusion/exclusion for three events.
00:12:03.800 --> 00:12:08.100
That is A union B union C.
00:12:08.100 --> 00:12:10.000
It was this complicated formula.
00:12:10.000 --> 00:12:16.700
It is the number things in A + the number of things in B + the number of things in C.
00:12:16.700 --> 00:12:19.000
Then, you have to subtract off all the intersection.
00:12:19.000 --> 00:12:27.600
A intersect B - A intersect C - B intersect C.
00:12:27.600 --> 00:12:32.300
As we saw on one of the beginning slides in this lecture, just a couple of slides ago.
00:12:32.300 --> 00:12:40.900
They have to add back in the intersection of all three of them, A intersect B intersect C.
00:12:40.900 --> 00:12:43.300
I want to go through and fill in all those numbers.
00:12:43.300 --> 00:12:48.200
Some of these were given to us in the first example, example 1.
00:12:48.200 --> 00:12:51.300
Go back and check those numbers, if you do not know where these come from.
00:12:51.300 --> 00:12:56.000
The number of people taking English was 158, we are told that in example 1.
00:12:56.000 --> 00:13:02.000
Remember, the people taking math was 120 and now we are told that the same college right here,
00:13:02.000 --> 00:13:05.000
100 people are taking history.
00:13:05.000 --> 00:13:12.500
Remember, people taking both English and Math, we found that out in the previous problem was 90.
00:13:12.500 --> 00:13:16.100
A intersect C is English and History.
00:13:16.100 --> 00:13:23.700
We are told that that is 80 people taking both English and History.
00:13:23.700 --> 00:13:25.800
Let me subtract off 80 there.
00:13:25.800 --> 00:13:30.600
And then, math and history is 75.
00:13:30.600 --> 00:13:38.700
And A intersect B intersect C is the people taking all three Math, English and History.
00:13:38.700 --> 00:13:41.700
We are told that there are 60 people taking all three classes.
00:13:41.700 --> 00:13:45.600
I’m going to add that 60 back in.
00:13:45.600 --> 00:13:51.200
It is just a quick matter of adding up the arithmetic and if you do,
00:13:51.200 --> 00:14:08.200
I think I already checked these numbers 270, 370, 280, 200, 125 + 60 is 185.
00:14:08.200 --> 00:14:12.500
That is how many students are taking all three classes.
00:14:12.500 --> 00:14:15.300
We are also asked how many are taking only history?
00:14:15.300 --> 00:14:21.100
I think the easiest way to figure that out is by drawing a diagram.
00:14:21.100 --> 00:14:28.600
Let me draw a diagram of all three classes represented there, math, English, and history.
00:14:28.600 --> 00:14:36.800
We will see if we can figure out just exactly how many students go in each different category there.
00:14:36.800 --> 00:14:49.900
I have got a group of students taking English, a group of students taking math, and a group of students taking history.
00:14:49.900 --> 00:14:54.000
There is my English group, there is my math group, and there is my history group.
00:14:54.000 --> 00:14:56.100
They are perfect circles but that is alright.
00:14:56.100 --> 00:15:01.500
I want to find whatever numbers I can now and I know that 60 are taking all three classes.
00:15:01.500 --> 00:15:03.800
I will write it from the inside out here.
00:15:03.800 --> 00:15:08.600
I know that 60 people are taking all three classes.
00:15:08.600 --> 00:15:17.200
I know from the previous example, from example 1, that there were 90 students taking both English and math.
00:15:17.200 --> 00:15:19.100
And we already accounted for 60 of them.
00:15:19.100 --> 00:15:23.400
That means that 30 students left over here in the English and math.
00:15:23.400 --> 00:15:27.400
In English and history, there are 80 students total.
00:15:27.400 --> 00:15:34.100
We already accounted for 60 of them so there must be 20 here that are taking English and history but not math.
00:15:34.100 --> 00:15:38.400
For math and history, we got 75 total.
00:15:38.400 --> 00:15:44.600
60 of them are also taking English that means 15 of them are taking math and history but not English.
00:15:44.600 --> 00:15:47.300
Let me go ahead and figure and fill in the others.
00:15:47.300 --> 00:15:57.100
For English, I see that I already got 110 accounted for but there is a 150 English students total.
00:15:57.100 --> 00:15:59.700
It must be 40 more outside here.
00:15:59.700 --> 00:16:06.600
From math, I see I got 90 + 15, a 105 total but there were 120 people taking Math.
00:16:06.600 --> 00:16:09.400
There must be 15 left over.
00:16:09.400 --> 00:16:15.300
And for history, I see that I got 20 + 60 + 15 that is 80 + 15.
00:16:15.300 --> 00:16:17.900
95 students total.
00:16:17.900 --> 00:16:23.700
It said that 100 freshmen are taking history.
00:16:23.700 --> 00:16:25.600
I have accounted for 95 of them.
00:16:25.600 --> 00:16:30.200
That must mean that there is 5 extra students left over here.
00:16:30.200 --> 00:16:34.500
I think the question said, how many are taking only history?
00:16:34.500 --> 00:16:46.700
The answer to that is that 5 students are taking history but not math or English.
00:16:46.700 --> 00:16:58.700
That is coming from that 5, right there.
00:16:58.700 --> 00:17:01.300
Let me remind you how we get everything here.
00:17:01.300 --> 00:17:04.500
We got three events here, we got English, math, and history.
00:17:04.500 --> 00:17:08.400
We are using our inclusion/exclusion rule for three events.
00:17:08.400 --> 00:17:16.600
And that is the formula that we had on one of the earlier slides for the inclusion/exclusion rule for three events, A union B union C.
00:17:16.600 --> 00:17:24.500
You add the individual events, you subtract off the intersections, and then you add back in the three way intersection.
00:17:24.500 --> 00:17:25.900
And I just fill then all the numbers.
00:17:25.900 --> 00:17:30.900
Some of these numbers I got from example 1 because it was the same example.
00:17:30.900 --> 00:17:36.000
Then, I filled in the new numbers that we are given here in example 2.
00:17:36.000 --> 00:17:38.600
And I add them up and I got 185.
00:17:38.600 --> 00:17:46.500
Another way to do that is to set up this diagram here and setup circles for English, math and history
00:17:46.500 --> 00:17:52.100
and figure out what the numbers of students are in each of these categories.
00:17:52.100 --> 00:17:54.200
To do that, you really want to work from the inside out.
00:17:54.200 --> 00:18:00.000
We start the 60 students in all three, and then we work our way out into figure out
00:18:00.000 --> 00:18:03.600
how many students are in each intersection, and we get those by subtracting.
00:18:03.600 --> 00:18:11.300
For example, this 20 came from the fact that there were 80 students taking English and history.
00:18:11.300 --> 00:18:16.700
We already accounted for 60 of them taking all three classes.
00:18:16.700 --> 00:18:19.900
That 20 was 80 -60.
00:18:19.900 --> 00:18:24.500
We have figured out this 30 right here and this 15 right here.
00:18:24.500 --> 00:18:29.600
By doing some more subtraction, we figure out that there are 40 students just taking English,
00:18:29.600 --> 00:18:42.900
15 students just taking Math, and 5 students just taking history which was the answer to the second part of the problem there.
00:18:42.900 --> 00:18:48.700
For example 3, we are going to keep going in a college setting but this time we are going to look at student ID numbers.
00:18:48.700 --> 00:18:54.500
In this particular small college, they range from 000 to 999 which really means there is
00:18:54.500 --> 00:19:01.200
a thousand numbers available because 1 through 999 and then one more for 000.
00:19:01.200 --> 00:19:08.300
The question is how many of these numbers have at least 1-3 and at least 1-4 in them?
00:19:08.300 --> 00:19:10.200
I want to set up some events to solve this.
00:19:10.200 --> 00:19:13.900
Let me go ahead and describe my events here.
00:19:13.900 --> 00:19:26.800
A is going to be the set of all numbers that have at least 1-3 in them.
00:19:26.800 --> 00:19:37.100
B will be the set of numbers that have at least 1-4 in them.
00:19:37.100 --> 00:19:44.400
By the way, some notation that I'm using here that you might not seem is this colon equals notation.
00:19:44.400 --> 00:19:48.500
Colon equals just means, when I'm defining a set.
00:19:48.500 --> 00:19:58.600
That means A is defined to be, whatever is appearing on the right.
00:19:58.600 --> 00:20:03.100
Defined to be whatever is appearing on the right.
00:20:03.100 --> 00:20:06.100
That is what that colon equals notation means.
00:20:06.100 --> 00:20:08.700
It is a notation that I borrowed from the Computer Sciences.
00:20:08.700 --> 00:20:14.500
It is very useful when you are programming to say this variable is defined to be some value.
00:20:14.500 --> 00:20:16.900
That is why I mean by that colon equals.
00:20:16.900 --> 00:20:25.000
If you do not like it, you can just use and equal sign and it essentially means the same thing.
00:20:25.000 --> 00:20:26.500
Let me keep going here.
00:20:26.500 --> 00:20:35.600
We are going to use inclusion/exclusion here and we are going to try to count A intersect B.
00:20:35.600 --> 00:20:43.300
We have been asked to find the number of ids that have at least 1-3 and at least 1-4.
00:20:43.300 --> 00:20:47.200
That really means we are going to count A intersect B.
00:20:47.200 --> 00:20:55.500
But inclusion/exclusion say we can count that if we can find A by itself and B by itself, and A union B.
00:20:55.500 --> 00:20:57.500
Each one of those is a little problem here.
00:20:57.500 --> 00:20:59.300
Let us try to count each one of those.
00:20:59.300 --> 00:21:05.800
A by itself, how many numbers have at least 1-3 in them?
00:21:05.800 --> 00:21:09.000
The easiest way to count that is to count the complement.
00:21:09.000 --> 00:21:26.400
It is 1000 numbers total - the numbers with no 3’s in them.
00:21:26.400 --> 00:21:31.600
Let us think about how many numbers have no 3’s in them.
00:21:31.600 --> 00:21:37.000
That means you are trying to build a three digit number and you are allowed to use any digit you like
00:21:37.000 --> 00:21:40.400
except you cannot use the digit 3.
00:21:40.400 --> 00:21:47.500
You got three digits here, if you cannot use the digit 3 and you have really only got 9 choices left,
00:21:47.500 --> 00:21:51.800
0-9 except the 3 for each of these possibilities.
00:21:51.800 --> 00:21:59.900
There are 9 possibilities here, 9 possibilities for the second digit and 9 possibilities for the third digit.
00:21:59.900 --> 00:22:07.400
This is, in total, 1000 – 9³.
00:22:07.400 --> 00:22:11.700
We are throwing out all the numbers that do not have any 3's in them,
00:22:11.700 --> 00:22:16.000
leaving us exactly the numbers that have at least 1-3 in them.
00:22:16.000 --> 00:22:24.200
9³ is 729, this is 1000 – 729.
00:22:24.200 --> 00:22:32.400
That is, 1000 – 729 is 271.
00:22:32.400 --> 00:22:37.100
For B, what is all the numbers that have at least 1 -4?
00:22:37.100 --> 00:22:44.500
Exactly the same reasoning applies, just instead of kicking out all the ones with the 3 in them,
00:22:44.500 --> 00:22:47.700
we are going to kick out the ones with 4 in them.
00:22:47.700 --> 00:22:53.500
To count those, we have 9 digits available because we kicked out the 4, instead of kicking out the 3.
00:22:53.500 --> 00:22:56.100
That is going work out exactly the same way.
00:22:56.100 --> 00:23:03.900
1000 – 9³ and again that is going to work out to 271.
00:23:03.900 --> 00:23:13.900
Since, I would like to know calculate A intersect B, the preliminary step to doing that is to calculate A union B,
00:23:13.900 --> 00:23:38.300
which means the number of ids that have at least 1-3 or at least 1-4 or both.
00:23:38.300 --> 00:23:39.800
That is what we have to try to count.
00:23:39.800 --> 00:23:42.800
That is quite difficult to count directly.
00:23:42.800 --> 00:23:48.200
It is hard to count the number of ids that have at least 1-3 or at least 1-4.
00:23:48.200 --> 00:23:57.200
The easy way to count it is to work backwards and start with 1000 numbers total and subtract off the complement of that set,
00:23:57.200 --> 00:24:14.200
which is all the numbers that have no 3’s and no 4’s.
00:24:14.200 --> 00:24:18.100
Let us try to count all the numbers with no 3’s and no 4’s.
00:24:18.100 --> 00:24:20.500
That is kind of similar to what we get above.
00:24:20.500 --> 00:24:27.800
We have a three digit number, we have all the digits available to us except there are no 3’s and no 4’s.
00:24:27.800 --> 00:24:33.300
There is 8 possibilities for each digit, 8 times 8 times 8.
00:24:33.300 --> 00:24:38.500
This is 1000 -8³.
00:24:38.500 --> 00:24:42.800
8³, if you know your powers of 2 very well turn out to be 512.
00:24:42.800 --> 00:24:53.800
1000 -512 and that is 488.
00:24:53.800 --> 00:24:57.600
Finally, we are in a position to use our formula for inclusion/exclusion.
00:24:57.600 --> 00:24:59.600
We are trying to count A intersect B.
00:24:59.600 --> 00:25:03.400
We want the numbers that have a 3 and have a 4 in them.
00:25:03.400 --> 00:25:13.500
Inclusion/exclusion says you add up all the a's, all the b’s, and then you subtract off the union.
00:25:13.500 --> 00:25:18.700
That was our second formula for inclusion/exclusion back on the very first slide of this lecture.
00:25:18.700 --> 00:25:20.400
You can go back and check that out.
00:25:20.400 --> 00:25:25.100
In this case, we have 271.
00:25:25.100 --> 00:25:27.800
Let me make that a little more obvious, what I’m writing there.
00:25:27.800 --> 00:25:36.600
271 + 271 – 488.
00:25:36.600 --> 00:25:51.400
271 + 271 is 5420 – 488, that is 42 + 12 which is 54.
00:25:51.400 --> 00:25:58.100
That is the number of student ID numbers that will have both a 3 and a 4 in them.
00:25:58.100 --> 00:26:02.600
They have at least 1-3 and 1-4 in them.
00:26:02.600 --> 00:26:05.400
That is our answer.
00:26:05.400 --> 00:26:07.600
Let me just highlight the key steps there.
00:26:07.600 --> 00:26:10.100
First thing here was to set up some events.
00:26:10.100 --> 00:26:15.700
We set up, we define an event A to be all the numbers with at least 1-3.
00:26:15.700 --> 00:26:19.600
Event B is all the numbers with at least 1-4.
00:26:19.600 --> 00:26:24.300
We are planning to use this inclusion/exclusion formula.
00:26:24.300 --> 00:26:29.700
We want to count the and of something which means we want to count an intersection.
00:26:29.700 --> 00:26:37.600
Our inclusion/exclusion formula for an intersection says that you have to add up the individual sets and then subtract off the union.
00:26:37.600 --> 00:26:42.600
I have got to count all the things in the individual sets and in the union.
00:26:42.600 --> 00:26:47.100
To find the individual sets, A is all the numbers with at least 1-3.
00:26:47.100 --> 00:26:51.200
It is quite tricky to count directly but it is easy to count the complement of that.
00:26:51.200 --> 00:26:53.100
That is what we are doing here.
00:26:53.100 --> 00:26:55.700
We are counting all the things with no 3’s in them.
00:26:55.700 --> 00:27:00.000
That is really a complement there.
00:27:00.000 --> 00:27:08.000
To get the number with no 3’s, you are building a number out of the 9 remaining digits, 0 through 9 but you cannot use a 3.
00:27:08.000 --> 00:27:15.300
There are 9 choices for each decimal place and that is why we got 9³ there.
00:27:15.300 --> 00:27:19.100
1000 -9³ simplifies down to 271.
00:27:19.100 --> 00:27:21.500
These are all the numbers that have at least 1-4.
00:27:21.500 --> 00:27:27.500
That is exactly the same reasoning, you are building a number out of 3 digits but you are not allowed to use 4.
00:27:27.500 --> 00:27:31.000
You end up with 271 again.
00:27:31.000 --> 00:27:38.500
A union B is all the numbers that have at least 1-3 or at least 1-4.
00:27:38.500 --> 00:27:43.600
Again, that is quite a difficult thing to count directly but you can count the compliment.
00:27:43.600 --> 00:27:47.900
The compliment means that you would have no 3’s and no 4’s.
00:27:47.900 --> 00:27:51.800
That is A union B complement right there.
00:27:51.800 --> 00:27:58.500
That means you are trying to build a number using all the digits except no 3’s and no 4’s.
00:27:58.500 --> 00:28:05.300
You are allowed to use 8 digits here, 8 digits here, 8 digits here, and you end up with 8³ numbers.
00:28:05.300 --> 00:28:09.000
I will subtract that from 1000 because that was the complement of what we want.
00:28:09.000 --> 00:28:11.600
You end up with 488.
00:28:11.600 --> 00:28:15.700
And that is just a matter of dropping those numbers into our inclusion/exclusion formula
00:28:15.700 --> 00:28:27.100
and simplifying down to 54 student ID numbers is our final answer there.
00:28:27.100 --> 00:28:35.200
Example 4, we have to figure out how many whole numbers between 1 and 1000 are divisible by 2, 3, or 5?
00:28:35.200 --> 00:28:37.600
Again, this is going to be inclusion/exclusion.
00:28:37.600 --> 00:28:39.100
We are going to have three events here.
00:28:39.100 --> 00:28:41.500
Let me go ahead and define what the events are.
00:28:41.500 --> 00:28:54.200
A is going to be the set of all numbers that are divisible by 2.
00:28:54.200 --> 00:28:58.300
Remember that notation with a colon equals, that means define to be.
00:28:58.300 --> 00:29:08.200
B is defined to be the set of all numbers divisible by 3.
00:29:08.200 --> 00:29:12.300
C is the set of all numbers divisible by 5.
00:29:12.300 --> 00:29:14.500
We are going to use inclusion/exclusion.
00:29:14.500 --> 00:29:32.900
We are trying to find the union of three events here because we want all the numbers that are divisible by at least 1 of 2, 3, or 5.
00:29:32.900 --> 00:29:41.000
You see or, you know you are counting union, A union B union C.
00:29:41.000 --> 00:29:46.800
Let me go ahead and write out the formula for the inclusion/exclusion formula for the union of three events.
00:29:46.800 --> 00:29:51.100
We discover this in the second slide of this topic.
00:29:51.100 --> 00:29:53.600
You can go back and check that out, if you do not remember it.
00:29:53.600 --> 00:30:03.300
It is everything in A + everything in B + everything in C.
00:30:03.300 --> 00:30:12.900
And I have to subtract off the intersections.
00:30:12.900 --> 00:30:16.600
A intersect B - A intersects C - B intersect C.
00:30:16.600 --> 00:30:25.200
And now you have to add in the intersection of all three, A intersect B intersect C.
00:30:25.200 --> 00:30:30.200
Now, we have to think how big each of these sets are.
00:30:30.200 --> 00:30:33.000
A is the set of numbers divisible by 2.
00:30:33.000 --> 00:30:37.300
How many numbers between 1 and 1000 are divisible by 2?
00:30:37.300 --> 00:30:52.100
Since, every other number is divisible by 2, the size of A is 1000 ÷ 2 which is 500.
00:30:52.100 --> 00:30:56.000
There is 500 numbers that are divisible by 2, 500 even numbers.
00:30:56.000 --> 00:30:58.300
How many are divisible by 3?
00:30:58.300 --> 00:31:06.000
It is essential 1000 ÷ 3 but that is not a whole number.
00:31:06.000 --> 00:31:11.300
What happens is it does not quite work because we have multiples of 3 every third number.
00:31:11.300 --> 00:31:15.800
But then at the end, we just get some extra numbers that do not give us anything.
00:31:15.800 --> 00:31:19.300
I’m going to round that down.
00:31:19.300 --> 00:31:21.400
This is the floor function notation.
00:31:21.400 --> 00:31:32.600
It just means I'm running it down to 999/3 and the reason I pick 999 is because it is a multiple of 3.
00:31:32.600 --> 00:31:40.600
That gives me 333 numbers divisible by 3.
00:31:40.600 --> 00:31:45.300
C is divisible by 5, how many numbers are divisible by 5?
00:31:45.300 --> 00:31:53.300
1000/5 and that is a whole number, that is just 200, + 200 here.
00:31:53.300 --> 00:32:02.300
A intersect B is where it starts to get interesting because A intersect B means, it is divisible by 2 and it is divisible by 3.
00:32:02.300 --> 00:32:17.300
Since 2 and 3 are relatively prime, if it is divisible by both of them, A intersect B really means that is divisible by 6.
00:32:17.300 --> 00:32:20.700
If it is divisible by both 2 and 3 then it is divisible by 6.
00:32:20.700 --> 00:32:22.400
It is a multiple of 6.
00:32:22.400 --> 00:32:26.300
How many numbers between 1 and 1000 are divisible by 6?
00:32:26.300 --> 00:32:30.400
Every 6th number is divisible by 6.
00:32:30.400 --> 00:32:33.800
You really have to look at 1000 ÷ 6.
00:32:33.800 --> 00:32:35.500
That is not a whole number.
00:32:35.500 --> 00:32:40.200
I’m going to use this 4 notation to round down.
00:32:40.200 --> 00:32:46.200
The largest number below 1000 that is divisible by 6 is 996.
00:32:46.200 --> 00:32:54.200
We can kind of throw out everything after 996 and just see how many multiples of 6 there are between 1 and 996.
00:32:54.200 --> 00:33:03.000
If we divide that by 6, 996/6 turns out to be 166.
00:33:03.000 --> 00:33:08.600
That is how many numbers there are between 1 and 1000 that are divisible by 6.
00:33:08.600 --> 00:33:13.900
That is what it means to be divisible by 2 and by 3.
00:33:13.900 --> 00:33:19.500
We are going to subtract of 166 here.
00:33:19.500 --> 00:33:25.100
For A intersect C, that is divisible by 2 and divisible by 5.
00:33:25.100 --> 00:33:34.600
If it is divisible by two and by 5 then you are divisible by 10.
00:33:34.600 --> 00:33:39.100
We are going to ask how many multiples of 10 are there between 1 and 1000?
00:33:39.100 --> 00:33:43.800
And of course, there are 1000 ÷ 10.
00:33:43.800 --> 00:33:46.200
I do not have to round that down since it is a whole number.
00:33:46.200 --> 00:33:50.900
There is 100 of those, -100.
00:33:50.900 --> 00:33:54.100
Finally, for B intersect C, that is not finally.
00:33:54.100 --> 00:33:59.100
I’m running out of space here.
00:33:59.100 --> 00:34:02.900
Let me carve out some space down here for myself.
00:34:02.900 --> 00:34:16.000
For B intersect C, it would be the set of numbers that are divisible by both 3 and 5.
00:34:16.000 --> 00:34:19.500
Those are being divisible by 15.
00:34:19.500 --> 00:34:24.400
I have to figure out how many numbers between 1 and 1000 are divisible by 15?
00:34:24.400 --> 00:34:26.400
Again, it is just all the multiples of 15.
00:34:26.400 --> 00:34:28.100
It is every 15th number.
00:34:28.100 --> 00:34:35.000
It is 1000/15 except that is not a whole number.
00:34:35.000 --> 00:34:38.600
We are going to throw out the last few numbers and I’m going to round down.
00:34:38.600 --> 00:34:45.300
When I cut it off at the last multiple of 15 before 1000 which is 990.
00:34:45.300 --> 00:34:55.800
990 ÷ 15 and that turns out be, 90 ÷ 15 is 6, 900 ÷ 15 is 60.
00:34:55.800 --> 00:35:02.000
That is 66 there for B intersect C.
00:35:02.000 --> 00:35:10.600
Finally, A intersect B intersect C, that means you are divisible by 2 and 3 and 5,
00:35:10.600 --> 00:35:26.100
which means you are divisible by the least common multiple of 2 and 3 and 5 which is 30.
00:35:26.100 --> 00:35:31.300
I want to find out how many numbers there are between about 1 and 1000 that are divisible by 30.
00:35:31.300 --> 00:35:33.600
Essentially, I just divide 1000 by 30.
00:35:33.600 --> 00:35:35.600
But again, it is not a whole number.
00:35:35.600 --> 00:35:39.400
I’m going to round down this one sided bracket notation.
00:35:39.400 --> 00:35:44.000
It is the floor function, it means you round down because you are cutting off any numbers
00:35:44.000 --> 00:35:46.500
at the end that would not be divisible by 30.
00:35:46.500 --> 00:35:53.400
The last multiple of 30 before 14000 is also 990.
00:35:53.400 --> 00:35:56.600
Let me throw away all the numbers between 990 and 1000.
00:35:56.600 --> 00:36:01.300
I will just keep the ones up through 990.
00:36:01.300 --> 00:36:05.400
990 ÷ 30 is 33.
00:36:05.400 --> 00:36:10.100
That is the set of numbers divisible by 2, 3, and 5.
00:36:10.100 --> 00:36:15.100
I want to add at the end here, 33.
00:36:15.100 --> 00:36:17.700
Now, it is just a matter of doing the arithmetic.
00:36:17.700 --> 00:36:38.100
500 + 333 + 200 is 1033 - 166 -100 -66 + 33.
00:36:38.100 --> 00:36:52.500
1033 + 33 -66 give us an even 1000 - 100 is 900 -166 is 734.
00:36:52.500 --> 00:36:54.400
That is our answer there.
00:36:54.400 --> 00:37:03.000
That is the number of whole numbers between 1 and 1000 that would be divisible by 2 or 3 or 5,
00:37:03.000 --> 00:37:09.200
or some combination of those prime numbers.
00:37:09.200 --> 00:37:13.300
That is our answer, let me show you again the steps we followed there.
00:37:13.300 --> 00:37:15.100
We first set up three events there.
00:37:15.100 --> 00:37:18.100
A is the stuff divisible by 2.
00:37:18.100 --> 00:37:20.900
B is the stuff divisible by 3.
00:37:20.900 --> 00:37:23.200
C is the stuff divisible by 5.
00:37:23.200 --> 00:37:30.500
I’m going to use the formula for inclusion/exclusion for 3 events to find all the numbers
00:37:30.500 --> 00:37:34.000
that are divisible by at least one of those things.
00:37:34.000 --> 00:37:35.700
I’m counting a union there.
00:37:35.700 --> 00:37:41.500
I’m counting all the stuff in A + all the stuff in B + all the stuff in C.
00:37:41.500 --> 00:37:43.700
Let me remind you how we counted that.
00:37:43.700 --> 00:37:46.500
A is all the multiples of 2.
00:37:46.500 --> 00:37:52.500
To see how many multiples of 2 there are, you just divide 1000 by 2 and you get 500.
00:37:52.500 --> 00:37:54.600
That is where that 500 came from.
00:37:54.600 --> 00:37:55.900
B is the multiples of 3.
00:37:55.900 --> 00:38:03.000
1000/3 does not go quite evenly, you have to round down to 333.
00:38:03.000 --> 00:38:08.400
C is 1000/5, the multiples of 5, there are 200 of them.
00:38:08.400 --> 00:38:15.100
A intersect B, you are looking at multiples of 2 and 3 because it is an intersection, it is N.
00:38:15.100 --> 00:38:20.000
If it is divisible by 2 and 3, then it is divisible by 6.
00:38:20.000 --> 00:38:23.300
We have to find the multiples of 6.
00:38:23.300 --> 00:38:26.900
We look at 1000 ÷ 6 which is not a whole number.
00:38:26.900 --> 00:38:31.000
Throw out all the numbers at the very end which are not visible by 6 anyway.
00:38:31.000 --> 00:38:39.000
And we just look at the last multiple of 6 is 996, divide that by 6 and get 166 multiples of 6 there.
00:38:39.000 --> 00:38:45.600
Similarly, A and C means divisible by 2 and 5, you are divisible by 10.
00:38:45.600 --> 00:38:49.900
Every 10th number is divisible by 10, there is 100 of them.
00:38:49.900 --> 00:38:55.300
B and C divisible by 3 and 5, these are divisible by 15.
00:38:55.300 --> 00:38:58.600
1000/15, once you round down is 66.
00:38:58.600 --> 00:39:01.200
That is where that 66 come from.
00:39:01.200 --> 00:39:10.200
A intersect B intersect C means you are divisible by all three numbers, 2, 3, and 5, which makes you divisible by 30.
00:39:10.200 --> 00:39:16.000
1000/30, we are going to throw out all the numbers at the end that are not multiples of 30.
00:39:16.000 --> 00:39:19.000
We will just stop at 990, the last multiple of 30.
00:39:19.000 --> 00:39:23.900
And then counting up to there, we get 990/30 is 33.
00:39:23.900 --> 00:39:35.600
That is just a matter of simplifying the numbers down and doing the arithmetic and coming up with our answer of 734 numbers.
00:39:35.600 --> 00:39:39.100
In our final example here, we are going out to a busy restaurant.
00:39:39.100 --> 00:39:42.300
They are serving 200 customers that night.
00:39:42.300 --> 00:39:45.100
I'm looking at it from restaurants point of view.
00:39:45.100 --> 00:39:51.600
125 of their customers ordered appetizers and 110 ordered desserts.
00:39:51.600 --> 00:39:59.500
170 of those customers ordered at least one of an appetizer and or a dessert.
00:39:59.500 --> 00:40:03.600
The question is how many ordered both appetizers and desserts?
00:40:03.600 --> 00:40:07.900
Quickly, I need to set up some events here.
00:40:07.900 --> 00:40:10.500
My colon equals, remember, means to find the B.
00:40:10.500 --> 00:40:19.500
I’m just cutting it for short and say A is the set of all people who ordered an appetizer.
00:40:19.500 --> 00:40:24.000
I can remember how to spell appetizer, it would help.
00:40:24.000 --> 00:40:30.300
B is the set of all the people that ordered dessert.
00:40:30.300 --> 00:40:33.700
And we are asked how many ordered both?
00:40:33.700 --> 00:40:38.600
Both means we are looking for people who ordered an appetizer and a dessert.
00:40:38.600 --> 00:40:40.400
That is the intersection.
00:40:40.400 --> 00:40:45.500
We are trying to calculate how many people ordered both?
00:40:45.500 --> 00:40:52.600
Our original rule for inclusion/exclusion on two events, if you go back and look at the very first slide in this lecture,
00:40:52.600 --> 00:40:55.000
we had the formula A intersect B.
00:40:55.000 --> 00:41:04.700
The number of things in A intersect B is the number of things in A + the number of things in B - the number of things in the union.
00:41:04.700 --> 00:41:09.200
We can calculate all of these directly from the problem stem.
00:41:09.200 --> 00:41:14.300
A is the number of people who had appetizers and it tells us that is 125.
00:41:14.300 --> 00:41:16.000
It tells us that up here.
00:41:16.000 --> 00:41:20.600
B is the number people who ordered desserts, there are 110 of them.
00:41:20.600 --> 00:41:25.500
But 170 people ordered at least one, that is the union right there.
00:41:25.500 --> 00:41:27.400
At least one means a union.
00:41:27.400 --> 00:41:31.500
We are going to subtract off 170 in here.
00:41:31.500 --> 00:41:33.400
Let us just do the arithmetic.
00:41:33.400 --> 00:41:40.900
We get 235 -170 is 65 people.
00:41:40.900 --> 00:41:49.900
We must have had 65 people ordering both an appetizer and desert at this particular restaurant.
00:41:49.900 --> 00:41:55.500
Ordered both, that means they are in the intersection of A and B.
00:41:55.500 --> 00:41:59.000
They are in both A and B.
00:41:59.000 --> 00:42:02.800
That was probably easier than some of the other problems here.
00:42:02.800 --> 00:42:05.200
Let me make sure that all the steps are really clear.
00:42:05.200 --> 00:42:11.000
First thing do is to set up events A and B, people who ordered appetizer, people who ordered dessert.
00:42:11.000 --> 00:42:16.600
And then we are asked how many people ordered both which means we are counting an intersection.
00:42:16.600 --> 00:42:19.400
We are going to count an intersection.
00:42:19.400 --> 00:42:24.300
We are going to use the formula for inclusion/exclusion that we had back in the very first slide.
00:42:24.300 --> 00:42:29.100
You count the individual events and then you subtract off the union.
00:42:29.100 --> 00:42:32.700
And we know the size of those because it is given to us in the stem of the problem.
00:42:32.700 --> 00:42:40.000
125 ordered appetizers, 110 ordered desserts, and 170 ordered at least one.
00:42:40.000 --> 00:42:43.300
That is the union right there, it is the 170.
00:42:43.300 --> 00:42:52.100
We just run the arithmetic here and we end up with 65 people ordering both appetizers and desserts.
00:42:52.100 --> 00:42:54.700
65 people in the intersection there.
00:42:54.700 --> 00:43:02.800
Interesting point about this problem is that this 200 customers total in the restaurant appears to be a red herring.
00:43:02.800 --> 00:43:07.300
It does not appear to be relevant at all to solving the problem.
00:43:07.300 --> 00:43:12.100
You do not always have to use every number in the problem to get your answer.
00:43:12.100 --> 00:43:16.100
Often the way, problems in homework exercises are set up.
00:43:16.100 --> 00:43:18.300
You use every number but it is not always true.
00:43:18.300 --> 00:43:22.600
Sometimes there is some red herring information there.
00:43:22.600 --> 00:43:26.500
That wraps up our lecture on inclusion/exclusion.
00:43:26.500 --> 00:43:27.900
I hope you will stick around for some more lectures.
00:43:27.900 --> 00:43:34.100
We got some good stuff coming up on independence and on Bayes' rule in the next couple of lectures.
00:43:34.100 --> 00:43:38.000
These are the probability lecture series here on www.educator.com.
00:43:38.000 --> 00:43:40.000
My name is Will Murray, thank you for watching, bye.