1.1 Additive and Multiplicative Principles 加法与乘法原理
本页译自 LibreTexts · Discrete Mathematics (Levin) 第 1.1 章。公式经 MathJax 渲染，自定义宏已注入。
Investigate! 探究！
- A restaurant offers 8 appetizers and 14 entrées. How many choices do you have if:
- you will eat one dish, either an appetizer or an entrée?
- you are extra hungry and want to eat both an appetizer and an entrée?
- Think about the methods you used to solve question 1. Write down the rules for these methods.
- Do your rules work? A standard deck of playing cards has 26 red cards and 12 face cards.
- How many ways can you select a card which is either red or a face card?
- How many ways can you select a card which is both red and a face card?
- How many ways can you select two cards so that the first one is red and the second one is a face card?
- 一家餐厅提供 8 种开胃菜和 14 种主菜。你有多少种选择，如果：
- 你只吃一道菜，要么是开胃菜，要么是主菜？
- 你格外饥饿，想同时吃一道开胃菜和一道主菜？
- 想一想你解第 1 题所用的方法，把这两种方法的规则写下来。
- 你的规则站得住脚吗？一副标准扑克牌有 26 张红色牌和 12 张人头牌。
- 有多少种选法可以选出一张「红色牌或人头牌」？
- 有多少种选法可以选出一张「既是红色牌又是人头牌」的牌？
- 有多少种选法可以依次抽出两张牌，使得第一张是红色牌、第二张是人头牌？
Consider this rather simple counting problem: at Red Dogs and Donuts, there are 14 varieties of donuts, and 16 types of hot dogs. If you want either a donut or a dog, how many options do you have? This isn't too hard, just add 14 and 16. Will that always work? What is important here?
Additive Principle 加法原理
The additive principle states that if event $A$ can occur in $m$ ways, and event $B$ can occur in $n$ disjoint ways, then the event “$A$ or $B$” can occur in $m + n$ ways.
It is important that the events be disjoint: i.e., that there is no way for $A$ and $B$ to both happen at the same time. For example, a standard deck of 52 cards contains $26$ red cards and $12$ face cards. However, the number of ways to select a card which is either red or a face card is not $26 + 12 = 38\text{.}$ This is because there are 6 cards which are both red and face cards.
Example 1
How many two letter “words” start with either A or B? (A word is just a string of letters; it doesn't have to be English, or even pronounceable.)
Solution
First, how many two letter words start with A? We just need to select the second letter, which can be accomplished in 26 ways. So there are 26 words starting with A. There are also 26 words that start with B. To select a word which starts with either A or B, we can pick the word from the first 26 or the second 26, for a total of 52 words.
The additive principle also works with more than two events. Say, in addition to your 14 choices for donuts and 16 for dogs, you would also consider eating one of 15 waffles? How many choices do you have now? You would have $14 + 16 + 15 = 45$ options.
Example 2
How many two letter words start with one of the 5 vowels?
Solution
There are 26 two letter words starting with A, another 26 starting with E, and so on. We will have 5 groups of 26. So we add 26 to itself 5 times. Of course it would be easier to just multiply $5\cdot 26\text{.}$ We are really using the additive principle again, just using multiplication as a shortcut.
Example 3
Suppose you are going for some fro-yo. You can pick one of 6 yogurt choices, and one of 4 toppings. How many choices do you have?
Solution
Break your choices up into disjoint events: $A$ are the choices with the first topping, $B$ the choices featuring the second topping, and so on. There are four events; each can occur in 6 ways (one for each yogurt flavor). The events are disjoint, so the total number of choices is $6 + 6 + 6 + 6 = 24\text{.}$
Note that in both of the previous examples, when using the additive principle on a bunch of events all the same size, it is quicker to multiply. This really is the same, and not just because $6 + 6 + 6 + 6 = 4\cdot 6\text{.}$ We can first select the topping in 4 ways (that is, we first select which of the disjoint events we will take). For each of those first 4 choices, we now have 6 choices of yogurt. We have:
Multiplicative Principle 乘法原理
The multiplicative principle states that if event $A$ can occur in $m$ ways, and each possibility for $A$ allows for exactly $n$ ways for event $B\text{,}$ then the event “$A$ and $B$” can occur in $m \cdot n$ ways.
The multiplicative principle generalizes to more than two events as well.
Example 4
How many license plates can you make out of three letters followed by three numerical digits?
Solution
Here we have six events: the first letter, the second letter, the third letter, the first digit, the second digit, and the third digit. The first three events can each happen in 26 ways; the last three can each happen in 10 ways. So the total number of license plates will be $26\cdot 26\cdot 26 \cdot 10 \cdot 10 \cdot 10\text{,}$ using the multiplicative principle.
Does this make sense? Think about how we would pick a license plate. How many choices we would have? First, we need to pick the first letter. There are 26 choices. Now for each of those, there are 26 choices for the second letter: 26 second letters with first letter A, 26 second letters with first letter B, and so on. We add 26 to itself 26 times. Or quicker: there are $26 \cdot 26$ choices for the first two letters.
Now for each choice of the first two letters, we have 26 choices for the third letter. That is, 26 third letters for the first two letters AA, 26 choices for the third letter after starting AB, and so on. There are $26 \cdot 26$ of these $26$ third letter choices, for a total of $(26\cdot26)\cdot 26$ choices for the first three letters. And for each of these $26\cdot26\cdot26$ choices of letters, we have a bunch of choices for the remaining digits.
In fact, there are going to be exactly 1000 choices for the numbers. We can see this because there are 1000 three-digit numbers (000 through 999). This is 10 choices for the first digit, 10 for the second, and 10 for the third. The multiplicative principle says we multiply: $10\cdot 10 \cdot 10 = 1000\text{.}$
All together, there were $26^3$ choices for the three letters, and $10^3$ choices for the numbers, so we have a total of $26^3 \cdot 10^3$ choices of license plates.
Careful: “and” doesn't mean “times.” For example, how many playing cards are both red and a face card? Not $26 \cdot 12\text{.}$ The answer is 6, and we needed to know something about cards to answer that question.
Another caution: how many ways can you select two cards, so that the first one is a red card and the second one is a face card? This looks more like the multiplicative principle (you are counting two separate events) but the answer is not $26 \cdot 12$ here either. The problem is that while there are 26 ways for the first card to be selected, it is not the case that for each of those there are 12 ways to select the second card. If the first card was both red and a face card, then there would be only 11 choices for the second card. [1] To solve this problem, you could break it into two cases. First, count how many ways there are to select the two cards when the first card is a red non-face card. Second, count how many ways when the first card is a red face card. Doing so makes the events in each separate case independent, so the multiplicative principle can be applied.
Counting functions 计数函数
How many functions $f:\{1,2,3,4,5\} \to \{a,b,c,d\}$ are there?
Solution
Remember that a function sends each element of the domain to exactly one element of the codomain. To determine a function, we just need to specify the image of each element in the domain. Where can we send 1? There are 4 choices. Where can we send 2? Again, 4 choices. What we have here is 5 “events” (picking the image of an element in the domain) each of which can happen in 4 ways (the choices for that image). Thus there are $4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 4^5$ functions.
This is more than just an example of how we can use the multiplicative principle in a particular counting question. What we have here is a general interpretation of certain applications of the multiplicative principle using rigorously defined mathematical objects: functions. Whenever we have a counting question that asks for the the number of outcomes of a repeated event, we can interpret that as asking for the number of functions from $\{1,2,\ldots, n\}$ (where $n$ is the number of times the event is repeated) to $\{1,2,\ldots,k\}$ (where $k$ is the number of ways that event can occur).
Counting With Sets 用集合计数
Do you believe the additive and multiplicative principles? How would you convince someone they are correct? This is surprisingly difficult. They seem so simple, so obvious. But why do they work?
To make things clearer, and more mathematically rigorous, we will use sets. Do not skip this section! It might seem like we are just trying to give a proof of these principles, but we are doing a lot more. If we understand the additive and multiplicative principles rigorously, we will be better at applying them, and knowing when and when not to apply them at all.
We will look at the additive and multiplicative principles in a slightly different way. Instead of thinking about event $A$ and event $B\text{,}$ we want to think of a set $A$ and a set $B\text{.}$ The sets will contain all the different ways the event can happen. (It will be helpful to be able to switch back and forth between these two models when checking that we have counted correctly.) Here's what we mean:
Example 6
Suppose you own 9 shirts and 5 pairs of pants.
- How many outfits can you make?
- If today is half-naked-day, and you will wear only a shirt or only a pair of pants, how many choices do you have?
- 你能搭配出多少套衣服？
- 如果今天是「半裸日」，你只穿一件衬衫或只穿一条裤子，你有多少种选择？
Answer
By now you should agree that the answer to the first question is $9 \cdot 5 = 45$ and the answer to the second question is $9 + 5 = 14\text{.}$ These are the multiplicative and additive principles. There are two events: picking a shirt and picking a pair of pants. The first event can happen in 9 ways and the second event can happen in 5 ways. To get both a shirt and a pair of pants, you multiply. To get just one article of clothing, you add.
Now look at this using sets. There are two sets, call them $S$ and $P\text{.}$ The set $S$ contains all 9 shirts so $|S| = 9$ while $|P| = 5\text{,}$ since there are 5 elements in the set $P$ (namely your 5 pairs of pants). What are we asking in terms of these sets? Well in question 2, we really want $|S \cup P|\text{,}$ the number of elements in the union of shirts and pants. This is just $|S| + |P|$ (since there is no overlap; $|S \cap P| = 0$). Question 1 is slightly more complicated. Your first guess might be to find $|S \cap P|\text{,}$ but this is not right (there is nothing in the intersection). We are not asking for how many clothing items are both a shirt and a pair of pants. Instead, we want one of each. We could think of this as asking how many pairs $(x,y)$ there are, where $x$ is a shirt and $y$ is a pair of pants. As we will soon verify, this number is $|S| \cdot |P|\text{.}$
From this example we can see right away how to rephrase our additive principle in terms of sets:
Additive Principle (with sets) 加法原理（集合表述）
Given two sets $A$ and $B\text{,}$ if $A \cap B = \emptyset$ (that is, if there is no element in common to both $A$ and $B$), then
$\begin{equation*} |A \cup B| = |A| + |B|. \end{equation*}$
This hardly needs a proof. To find $A \cup B\text{,}$ you take everything in $A$ and throw in everything in $B\text{.}$ Since there is no element in both sets already, you will have $|A|$ things and add $|B|$ new things to it. This is what adding does! Of course, we can easily extend this to any number of disjoint sets.
From the example above, we see that in order to investigate the multiplicative principle carefully, we need to consider ordered pairs. We should define this carefully:
Cartesian Product 笛卡尔积
Given sets $A$ and $B\text{,}$ we can form the set $A \times B = \{(x,y) \mid x \in A \wedge y \in B\}$ to be the set of all ordered pairs $(x,y)$ where $x$ is an element of $A$ and $y$ is an element of $B\text{.}$ We call $A \times B$ the Cartesian product of $A$ and $B\text{.}$
Example 7
Let $A = \{1,2\}$ and $B=\{3,4,5\}\text{.}$ Find $A \times B\text{.}$
Answer
We want to find ordered pairs $(a,b)$ where $a$ can be either $1$ or $2$ and $b$ can be either 3, 4, or 5. $A \times B$ is the set of all of these pairs:
$\begin{equation*} A \times B = \{(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\} \end{equation*}$
The question is, what is $|A \times B|\text{?}$ To figure this out, write out $A \times B\text{.}$ Let $A = \{a_1,a_2, a_3, \ldots, a_m\}$ and $B = \{b_1,b_2, b_3, \ldots, b_n\}$ (so $|A| = m$ and $|B| = n$). The set $A \times B$ contains all pairs with the first half of the pair being some $a_i \in A$ and the second being one of the $b_j \in B\text{.}$ In other words:
$\begin{align*} A \times B = & (a_1, b_1), (a_1, b_2), (a_1, b_3), \ldots (a_1, b_n),\\ & (a_2, b_1), (a_2, b_2), (a_2, b_3), \ldots, (a_2, b_n),\\ & (a_3, b_1), (a_3, b_2), (a_3, b_3), \ldots, (a_3, b_n),\\ & \vdots\\ & (a_m, b_1), (a_m, b_2), (a_m, b_3), \ldots, (a_m, b_n). \end{align*}$
Notice what we have done here: we made $m$ rows of $n$ pairs, for a total of $m \cdot n$ pairs.
Each row above is really $\{a_i\} \times B$ for some $a_i \in A\text{.}$ That is, we fixed the $A$-element. Broken up this way, we have
$\begin{equation*} A \times B = (\{a_1\} \times B) \cup (\{a_2\} \times B) \cup (\{a_3\}\times B) \cup \cdots \cup (\{a_m\} \times B). \end{equation*}$
So $A \times B$ is really the union of $m$ disjoint sets. Each of those sets has $n$ elements in them. The total (using the additive principle) is $n + n + n + \cdots + n = m \cdot n\text{.}$
To summarize:
Multiplicative Principle (with sets) 乘法原理（集合表述）
Given two sets $A$ and $B\text{,}$ we have $|A \times B| = |A| \cdot |B|\text{.}$
Again, we can easily extend this to any number of sets.
Principle of Inclusion/Exclusion 容斥原理
Investigate!
A recent buzz marketing campaign for Village Inn surveyed patrons on their pie preferences. People were asked whether they enjoyed (A) Apple, (B) Blueberry or (C) Cherry pie (respondents answered yes or no to each type of pie, and could say yes to more than one type). The following table shows the results of the survey.
| Pies enjoyed: | A | B | C | AB | AC | BC | ABC |
|---|---|---|---|---|---|---|---|
| Number of people: | 20 | 13 | 26 | 9 | 15 | 7 | 5 |
How many of those asked enjoy at least one of the kinds of pie? Also, explain why the answer is not 95.
While we are thinking about sets, consider what happens to the additive principle when the sets are NOT disjoint. Suppose we want to find $|A \cup B|$ and know that $|A| = 10$ and $|B| = 8\text{.}$ This is not enough information though. We do not know how many of the 8 elements in $B$ are also elements of $A\text{.}$ However, if we also know that $|A \cap B| = 6\text{,}$ then 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 \setminus B$ and 2 elements in $B \setminus A\text{.}$ Now these three sets are disjoint, so we can use the additive principle to find the number of elements in $A \cup B\text{.}$ It is $6 + 4 + 2 = 12\text{.}$
This will always work, but drawing a Venn diagram is more than we need to do. In fact, it would be nice to relate this problem to the case where $A$ and $B$ are disjoint. Is there one rule we can make that works in either case?
Here is another way to get the answer to the problem above. Start by just adding $|A| + |B|\text{.}$ This is $10 + 8 = 18\text{,}$ which would be the answer if $|A \cap B| = 0\text{.}$ We see that we are off by exactly 6, which just so happens to be $|A \cap B|\text{.}$ So perhaps we guess,
$\begin{equation*} |A \cup B| = |A| + |B| - |A \cap B|. \end{equation*}$
This works for this one example. Will it always work? Think about what we are doing here. We want to know how many things are either in $A$ or $B$ (or both). We can throw in everything in $A\text{,}$ and everything in $B\text{.}$ This would give $|A| + |B|$ many elements. But of course when you actually take the union, you do not repeat elements that are in both. So far we have counted every element in $A \cap B$ exactly twice: once when we put in the elements from $A$ and once when we included the elements from $B\text{.}$ We correct by subtracting out the number of elements we have counted twice. So we added them in twice, subtracted once, leaving them counted only one time.
In other words, we have:
Cardinality of a union (2 sets) （两个集合）并集的基数
For any finite sets $A$ and $B\text{,}$
$\begin{equation*} |A \cup B| = |A| + |B| - |A \cap B|. \end{equation*}$
We can do something similar with three sets.
Example 8
An examination in three subjects, Algebra, Biology, and Chemistry, was taken by 41 students. The following table shows how many students failed in each single subject and in their various combinations:
| Subject: | A | B | C | AB | AC | BC | ABC |
|---|---|---|---|---|---|---|---|
| Failed: | 12 | 5 | 8 | 2 | 6 | 3 | 1 |
How many students failed at least one subject?
Solution
The answer is not 37, even though the sum of the numbers above is 37. For example, while 12 students failed Algebra, 2 of those students also failed Biology, 6 also failed Chemistry, and 1 of those failed all three subjects. In fact, that 1 student who failed all three subjects is counted a total of 7 times in the total 37. To clarify things, let us think of the students who failed Algebra as the elements of the set $A\text{,}$ and similarly for sets $B$ and $C\text{.}$ The one student who failed all three subjects is the lone element of the set $A \cap B \cap C\text{.}$ Thus, in Venn diagrams:
Now let's fill in the other intersections. We know $A\cap B$ contains 2 elements, but 1 element has already been counted. So we should put a 1 in the region where $A$ and $B$ intersect (but $C$ does not). Similarly, we calculate the cardinality of $(A\cap C) \setminus B\text{,}$ and $(B \cap C) \setminus A\text{:}$
Next, we determine the numbers which should go in the remaining regions, including outside of all three circles. This last number is the number of students who did not fail any subject:
We found 5 goes in the “$A$ only” region because the entire circle for $A$ needed to have a total of 12, and 7 were already accounted for. Similarly, we calculate the “$B$ only” region to contain only 1 student and the “$C$ only” region to contain no students.
Thus the number of students who failed at least one class is 15 (the sum of the numbers in each of the eight disjoint regions). The number of students who passed all three classes is 26: the total number of students, 41, less the 15 who failed at least one class.
Note that we can also answer other questions. For example, now many students failed just Chemistry? None. How many passed Algebra but failed both Biology and Chemistry? This corresponds to the region inside both $B$ and $C$ but outside of $A\text{,}$ containing 2 students.
Could we have solved the problem above in an algebraic way? While the additive principle generalizes to any number of sets, when we add a third set here, we must be careful. With two sets, we needed to know the cardinalities of $A\text{,}$ $B\text{,}$ and $A \cap B$ in order to find the cardinality of $A \cup B\text{.}$ With three sets we need more information. There are more ways the sets can combine. Not surprisingly then, the formula for cardinality of the union of three non-disjoint sets is more complicated:
Cardinality of a union (3 sets) （三个集合）并集的基数
For any finite sets $A\text{,}$ $B\text{,}$ and $C\text{,}$
$\begin{equation*} |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{equation*}$
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.
Returning to our example above, we have $|A| = 12\text{,}$ $|B| = 5\text{,}$ $|C| = 8\text{.}$ We also have $|A \cap B| = 2\text{,}$ $|A \cap C| = 6\text{,}$ $|B \cap C| = 3\text{,}$ and $|A \cap B \cap C| = 1\text{.}$ Therefore:
$\begin{equation*} |A \cup B \cup C| = 12 + 5 + 8 - 2 - 6 - 3 + 1 = 15 \end{equation*}$
This is what we got when we solved the problem using Venn diagrams.
This process of adding in, then taking out, then adding back in, and so on is called the Principle of Inclusion/Exclusion, or simply PIE. We will return to this counting technique later to solve for more complicated problems (involving more than 3 sets).