Probability: Inclusion-Exclusion Principle

Inclusion-Exclusion Principle

Before we get to practice word problems using the inclusion-exclusion principle, it might help to see what the principle looks like in a picture.

With the inclusion-exclusion principle, we're going to use our knowledge of what's in each part of the Venn diagram to solve for a missing value.

Let's try an example.

Before we start trying to find $n(B),$ let's fill in what we already know on our diagram.

Now, let's get down to finding out what $n(B)$ is. This is the number that we'll put in set B, the purple circle.

There's a pretty easy formula to follow every time. Here it is:

If we plug the numbers in from our picture, here's what we get:

$$35 = 17 + n(B) - 6$$

Now, let's try this inclusion-exclusion principle with a word problem.

Let's start by creating a Venn diagram showing the info we've been given.

We're almost done! Let's look again at the equation to solve inclusion-exclusion problems.

When we plug our values in, we end up with:

$$14 = 12 + 9 - n(A \cap B).$$

Principles of Inclusion and Exclusion

Let's say we are trying to count the number of students in a class. The only data we have is that everyone in the class plays a sport. $12$ people play basketball, $16$ people play baseball, and $4$ people play both. How many people are in the class? At first this seems easy, just add up all the numbers and there are $32$ people in the class, right? Well it isn't that simple...

First let's look at our data. We know there are $12$ people who play basketball, but $4$ of those people ALSO play baseball. So we know we have already counted $4$ of the baseball people already. So in order to not double count anyone, we will subtract $4$ people from the $16$ people playing baseball. Therefore we have:

$$12 + 16 - 4 = 24$$

people in total. This can also be seen in a Venn Diagram.

We call this method of solving problems the Inclusion-Exclusion Principle.

However, the Inclusion-Exclusion Principle goes farther than that! What about if we have three sports? By now we need to use some basic set notation! A set is a group of things.

By the way, if you have a set A and a set B, the set of all elements that are either in A or B, is called $A\cup B.$ The set of all elements that are in both A and B is known as $A\cap B.$ The set that is NOT A is known as $A ^ \prime$

You can probably guess what $A \cup B \cup C \cup D \cup E \cup F$ means!

So the example with basketball and baseball can be condensed to one line. Here it is: $A \cup B = A + B - (A \cap B).$

So maybe there's a formula for $A \cup B \cup C?$ Maybe? This is a real brain teaser, but I suggest you have a go at it before I show you!

Okay, compare it to this: $A \cup B \cup C \\= A + B + C - (A \cap B ) - (A \cap C ) - (B \cap C ) + ( A \cap B \cap C ).$

And through this: try and find a formula for $A \cup B \cup C \cup D.$

There is a pattern. The formula is lengthy, but I'll list it out anyway! $A \cup B \cup C \cup D \\= A + B + C + D - (A \cap B) - (A \cap C) - (A \cap D) - (B \cap C)\\ - (B \cap D) - (C \cap D)$ $+ (A \cap B \cap C) + (A \cap B \cap D) + (A \cap C \cap D) + (B \cap C \cap D)$ $- (A \cap B \cap C \cap D).$

So to get the union of $n$ sets, you add all the sets, subtract the intersections of all pairs of these sets, add the intersections of all trebles of these sets, subtract all the intersections of all quadruples of these sets, add all the intersections of all quintuples of these sets, until you add or subtract the intersection of all the sets.

The statement above is the inclusion exclusion principle.

Introduction

Before we get started let's have a brief review of Venn diagrams. Venn diagrams are those circle things that overlap. Remember?

Set $A$ is the left circle, set $B$ is the right circle, and the space they overlap is the set that contains both $A$ and $B.$

We also have some notation: $\cup$ and $\cap$

The union is the number that can be either $A$ or $B.$ We denote it with the u-shape $\cup$ as $A\cup B$. Think "u" for union. The union of all the sets will be equal to the total amount of elements of each set.

The intersection holds the elements that are members of both $A$ and $B.$ This is the overlap slice. We denote it with the n-shape $\cap$ as $A\cap B$. Think "n" for intersection.

Now we introduce the Inclusion-Exclusion Principle with this in mind.

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a way to relate the set A, the set B, and the intersection to the union.

It says that if we add the elements in Set $A$ to the elements of Set $B$ and subtract the elements of $A\cap B$ (intersection) we get the total number of elements or the union, $A\cup B$.

$$A\cup B=A+B-A\cap B$$

Example

Suppose you ask $35$ people if they own a dog or a cat. $23$ of them say they only own a dog and $16$ say they only own a cat. How many own both a cat and a dog?

We can use our equation to figure this out. $$\begin{align} A\cup B&=A+B-A\cap B\\ 35&=23+16-A\cap B\\ A\cap B&=23+16-35\\ A\cap B&=4 \end{align}$$

So we know that $4$ of those people own both a dog and a cat! Now that is important information. Make friends with those $4$ people.

Probability

We can use the inclusion-exclusion principle in tandem with probability. The formula is almost identical too. $$P(A\cup B)=P(A)+P(B)-P(A\cap B)$$ Which means the probability of the union is equal to the probability of $A$ plus the probability of $B$ minus the probability of the intersection. In order to find the probability of the intersection we must multiply $P(A)$ and $P(B)$ together. Thus, $$\begin{align} P(A\cup B)&=P(A)+P(B)-P(A\cap B)\\ &=P(A)+P(B)-P(A) \cdot P(B) . \end{align}$$

Example

Suppose a neighborhood has a $50\%$ chance that a household has a pet. There's a $35\%$ chance they own a dog and a $25\%$ chance of owning a cat. What is the probability that they own both a dog and a cat?

We can use our i-e principle! $$\begin{align} P(A\cup B)&=P(A)+P(B)-P(A\cap B)\\ 0.5&=0.35+0.25-P(A\cap B)\\ P(A\cap B)&=0.35+0.25-0.5\\ P(A\cap B)&=0.1 \end{align}$$

There's a $10\%$ chance that if someone owns a pet, they own both a dog and a cat. I don't know about you but I wouldn't want to move into a neighborhood with that low of odds.

(Video) Ch9Pr4: Inclusion/Exclusion Principle

by MathsStatsUNSW

In this video, we walk through a problem that uses the inclusion-exclusion principle.

$\large{\text{Summary}}$

We have $150$ students and $3$ beer bands: $A, B, C$.

Given information:

• $58$ students drink $A$

• $49$ students drink $B$

• $57$ students drink $C$

• $14$ students drink $A\cap{C}$

• $13$ students drink $A\cap{B}$

• $17$ students drink $B\cap{C}$

• $4$ students drink $A\cap{B}\cap{C}$

How many students drink none of the beers?

We can do this problem with venn diagrams which is seen in the video, or we can use the inclusion-exclusion principle.

To find how many students drink none of the beers, we want the compliment of the union of all the students that drink all the beers. The formula is $$A\cup{B}\cup{C}=A+B+C-(A\cap{B})-(A\cap{C})-(B\cap{C})+(A\cap{B}\cap{C})$$

We can plug in the numbers given above to get the number of students that drink beer $A$, $B$, or $C$. We see, $$A\cup{B}\cup{C}=58+49+57-14-13-17+4=124$$ Now, to find the number of students that don't drink any beer. We find the compliments of $A\cup{B}\cup{C}$. The compliment is found by taking the total number of students and subtracting the amount of students that drink beers $A$, $B$, or $C$. This means $150-A\cup{B}\cup{C}$. So, $150-124=126$

$126$ students drink none of the beers!