Discrete Mathematics An Open Introduction, 4th Edition

In Section 3.2 we explored the sum principle as a way of combining two (or more) sets of disjoint outcomes. What happens if the outcomes are not disjoint?

Something different needs to be done. For example, when counting the number of playing cards that are either face cards or red cards, we cannot apply the sum principle to claim there are $12+26=38$ cards. The problem is exactly that six cards are both face cards and red cards. There are a few different ways we can handle this that we will explore in this section.

To understand how to deal with combining sets of outcomes that are not disjoint, it will be helpful to use some notation from set theory, which we will briefly review here.

Let $A$ be the set of outcomes for the first event and $B$ be the set of outcomes for the second event. When we ask for the number of ways either event can happen, the new set of outcomes consists of all outcomes that are in $A\text{,}$ or $B\text{,}$ or both. This is nothing more than the union of the set $A$ and $B\text{,}$ written $A\cup B\text{.}$

The sum principle only applies when no outcome belongs to both events. The elements that are common to sets $A$ and $B$ are the sets in their intersection, written $A\cap B\text{.}$ The intersection of two sets is itself a set. If sets $A$ and $B$ are disjoint, then there are no elements in the intersection, so the intersection is the empty set, written $\mathrm{\varnothing }\text{.}$

We are counting the number of outcomes, so what we are really interested in is the size (or cardinality) of the sets. We write the size of a set $X$ as $\left|X\right|\text{.}$

With this notation in hand, we can restate the sum principle as follows.

Now consider what happens to the sum principle when the sets are NOT disjoint. Suppose we want to find $|A\cup B|$ and know that $\left|A\right|=10$ and $\left|B\right|=8\text{.}$ If we knew that the sets were disjoint, then $|A\cup B|$ would be 18. But if we don’t have that the sets are disjoint, we need more information We must know how many of the 8 elements in $B$ are also elements of $A\text{.}$ Suppose we also know that $|A\cap B|=6\text{.}$ Now we can say exactly how many elements are in $A\text{,}$ and, of those, how many are in $B$ and how many are not (6 of the 10 elements are in $B\text{,}$ so 4 are in $A$ but not in $B$). We could fill in a Venn diagram as follows:

This says there are 6 elements in $A\cap B\text{,}$ 4 elements in $A$ but not $B$ (which we can write as $|A\setminus B|=4$), and 2 elements in $B$ but not $A$ (written $|B\setminus A|=2$). Now these three sets are disjoint, so we can use the sum principle to find the number of elements in $A\cup B\text{.}$ It is $6+4+2=12\text{.}$

We can do something similar with three sets.

It would be nice to write an algebraic formula that captures what we have done in the previous examples. Even better would be for this algebraic formula to be a generalization of the case where the sets are disjoint.

Consider again the example where $\left|A\right|=10\text{,}$ $\left|B\right|=8$ and $|A\cap B|=6\text{.}$ We said that $|A\cup B|=12\text{,}$ found by adding $4+6+2\text{.}$

In other words, we have:

For three sets, we can also count the elements in the union by carefully removing elements we have counted multiple times. Since there are more ways for the sets to overlap, the formula is more complicated.

To determine how many elements are in at least one of $A\text{,}$ $B\text{,}$ or $C$ we add up all the elements in each of those sets. However, when we do that, any element in both $A$ and $B$ is counted twice. Also, each element in both $A$ and $C$ is counted twice, as are elements in $B$ and $C\text{,}$ so we take each of those out of our sum once. But now what about the elements which are in $A\cap B\cap C$ (in all three sets)? We added them in three times, but also removed them three times. They have not yet been counted. Thus we add those elements back in at the end.

Everything we have considered so far in this section has been about how the sum principle applies when the sets of outcomes are not disjoint. Do we need to be similarly worried about overlaps when applying the product principle?

Not really.

One use of the product principle is to compute probabilities, and in that context, we do make a distinction between events being independent or dependent. We will explore this more in Section 3.7. Essentially, to find the probability of two events occuring, we can multiply their respective probabilities if and only if the two events are independent: if the outcome of one event does not affect the outcome of the other.

While finding probability is closely related to counting outcomes, the product principle itself does not require that sets of outcomes be disjoint or make a distinction between dependent or independent events. What does matter is that the number of outcomes for the second event does not change based on which outcome was the result of the first event.

A distinction we do often make when applying the product principle is whether the outcomes of events can be “repeated.” Consider the following example.

We will explore problems such as the previous example in much more depth next in Section 3.4. Before that though, here is a final example of where the product principle does NOT easily work.

We will see how to answer the counting problem above in the case that letters can be repeated in Section 3.5. If we restricted the question further and required that the letters be distinct (and in alphabetical order), we already know how to answer the question. Since for any set of three letters, there is exactly one 3-letter word that has those letters in alphabetical order, we can simply count the number of sets of three letters. This is $(\genfrac{}{}{0ex}{}{26}{3})\text{.}$ Then we just look at Pascal’s triangle to find the value... oh shoot. Our triangle doesn’t go down that far. I guess we should think of a way to compute the value without the triangle. Read on!