Rule of sum and rule of product

Imagine that you go to a bookshop and see two textbooks on computer science, and three on mathematics. How many choices do you have if you want to buy just one textbook? In how many ways can you buy exactly one computer science textbook and one math textbook?

This example problem falls under combinatorics, which is a branch of mathematics that deals with counting. Two intuitive rules that are useful for solving such combinatorial problems are the rule of sum and rule of product. These rules are also "building blocks" for more complex concepts.

In case you're curious, the answer to the first question is $5$ and the answer to the second is $6$. Keep reading to learn how to solve these kinds of problems.

Rule of sum

Let's revisit the problem from the introduction. You have the choice of $2$ computer science textbooks and $3$ math textbooks. If you want to buy only one textbook, then you have $2+3=5$ choices. It is important to note that a textbook can fall into only one category: either computer science or math. Use the rule of sum to solve this problem.

Let's use set theory. If $A$ is the set of ways to do one task and $B$ is the set of ways to do another task, and if $A$ and $B$ are disjoint, then the ways to do either the first or second task are $A \cup B$ (the union of set A and B). The rule of sum states that the number of elements in the union of these two sets is equal to the sum of the number of elements in the individual sets. Note that $|A|$ represents the cardinality of the set $A$.$$|A \cup B| = |A| + |B|$$

Rule of product

Let's go back to our bookshop problem. How do you calculate the number of ways you can buy one computer science textbook and one math textbook? Let's draw a tree to depict our scenario. Also, let's assume that you choose the computer science textbook first and then the math one. The possible ways for the books to be bought are represented by the distinct paths from the root to the leaf of the tree. In this tree there are $6$ such distinct paths. Since there are $2$ choices for the first book and $3$ for the second, there are $2 \cdot 3=6$ ways to buy both books. We used the rule of product to solve this problem.

In terms of set theory, if $A$ is the set of ways to do one task and $B$ is the set of ways to do another task, then making a choice $a$ from $A$ and a choice $b$ from $B$ can be represented as the ordered pair $(a,b)$. We denote all possible pairs with $A \times B$ and call it the Cartesian product. The rule of product says that the cardinality of the Cartesian product of sets $A$ and $B$ is equal to the product of the cardinalities of the individual sets.

$$|A \times B| = |A| \cdot |B|$$

Difference rule

Let $C$ be a subset of set $A$. If the number of elements in both $A$ and $C$ are known, then the number of elements that are in $A$ but not in $C$ can be computed as $$|A-C|=|A|-|C|$$

The difference rule follows immediately from the rule of sum. If $C$ is a subset of $A$, then $A-C$ and $C$ have no elements in common. So, $C \cup (A-C) = A$. By the rule of sum,

$$|C| + |A-C|=|A|$$

Here is an example to illustrate the difference rule. How many three-digit integers (from $100$ to $999$ inclusive) are there that have repeating digits?
On first thought, you might try to count all the integers that have repeating digits. These would include integers with $3$ repeating digits and $2$ repeating digits. For the integers with $2$ repeating digits, the non-repeating digit could occur as the first, second, or third digit. Wow, this is getting complicated!

Instead, let's figure out how many three-digit integers don't have repeating digits. Then subtract that amount from the total number of three-digit integers.

Let $S$ be the set of all three-digit integers and $N$ be the set of all three-digit integers with no repeating digits. Then $S-N$ is the set of all three-digit integers that have repeating digits.

Firstly, you need to figure out how many three-digit integers there are from $100$ to $999$. The first digit of every three-digit integer must be from the set $\{1, 2, …, 9\}$ (in other words, it cannot be $0$). The second and third digits are from the set $\{0,1, 2, …, 9\}$. By the rule of product, there are $9 \cdot 10 \cdot 10 = 900$ such numbers. So, $|S| = 900$.

Now, you need to figure out how many three-digit integers have no repeating digits. For the first digit, there are $9$ possibilities. For the second digit there are $9$ possibilities since it can be $0$ but cannot be the same as the first digit. Similarly, for the third digit there are $8$ possibilities as it has to be different from the first two digits. By the rule of product, there are $9 \cdot 9 \cdot 8 = 648$ such numbers. Therefore, $|N| = 648$.

Using the difference rule, you can calculate how many three-digit integers have repeating digits. $$|S-N| = |S| - |N| = 900-648 = 252$$Thus, there are $252$ three-digit integers that have repeating digits.

Example using both rule of sum and rule of product

At a restaurant, you can buy a meal which consists of one drink and one food item. For the drink, you can choose from $3$ hot beverages and $5$ cold beverages. For the food item, you can choose from $4$ types of sandwiches, $6$ types of pizzas, and $2$ types of salads. How many possible meals can you choose from?

Here's the solution:
First, pick one beverage from $3$ hot beverages and $5$ cold beverages. Using the rule of sum, you have $3+5 = 8$ options for your drink.
Next, pick one food item from $4$ sandwiches, $6$ pizzas, and $2$ salads. Again, using the rule of sum, you have $4+6+2 = 12$ options for your food item.
Since you have 8 drink options and 12 food item options, you have $8 \cdot 12 = 96$ options for your meal. We use the rule of product here, because the task of choosing a drink and the task of choosing a food item are both performed.

Conclusion

Suppose that there are $n$ choices for one task and $m$ choices for another independent task.

Use the rule of sum in situations when you must perform one task from a list of independent tasks. You can calculate the number of ways you can select a task through addition ($n+m$). The difference rule is a special case of the rule of sum, and it allows reaching the desired solution by counting "bad" options (that is, the desired set's complement) and subtracting them from the total number of options.

Apply the rule of product when you must perform multiple tasks one after the other. You can calculate the number of ways you can perform these multiple tasks through multiplication ($n \cdot m$).