Skip to main content

Chapter 16 Addition Principle and Multiplication Principle

  • Addition Principle (Sum Principle): If \(A\) and \(B\) are disjoint sets then

    \begin{equation*} |A \cup B| = |A| + |B|. \end{equation*}

  • Generalized Addition Principle: If \(A_1, A_2, \ldots, A_k\) are pairwise disjoint then

    \begin{equation*} | A_1 \cup A_2 \cup \cdots A_k| = |A_1| + |A_2| + \cdots |A_k|. \end{equation*}

  • Multiplication Principle (Product Principle): If \(A\) and \(B\) are sets then

    \begin{equation*} |A \times B| = |A| \cdot |B| \end{equation*}

  • Generalized Multiplication Principle If \(A_1, A_2, \ldots, A_k\text{,}\) are sets then

    \begin{equation*} |A_1 \times A_2 \times \cdots \times A_k | = |A_1| \cdot |A_2| \cdots |A_k|. \end{equation*}

Exercises Practice Problems

1. License Plates.

License plates in the Netherlands consist of three groups of two characters (either letters or numbers). Two of the groups must be of one type and the third group must be of the other. For example, the following are all valid license plates: AB-12-CD, 12-34-AB, 12-AB-34 How many possible license plates are there? Solution.

There are 6 different cases to consider:

\begin{equation*} \begin{array}{ccc} XX-XX-## & XX-##-XX & ##-XX-XX \\ XX-##-## & ##-##-XX & ##-XX-## \end{array} \end{equation*}

For each of the first three types, the product principle tells us that the number of license plates of that type is \((26^4)(10^2)\text{.}\) For each of the second three types, the product principle tells us that the number of license plates of that type is \((26)^2(10^4)\text{.}\) Therefore, by the addition principle, the total number of license plates is

\begin{equation*} 3 \cdot (26^4)(10^2) + 3 \cdot (26^2)(10^4) \end{equation*}

2. Restaurants.

I have three favorite restaurants in St Paul. Each of them has a choice of 3 kinds of soup, 4 kinds of salad and 7 different entrees.

  1. At The Crunchy Frog, you get a choice of soup or salad with your entree (choose one, not both). How many different meals can I order at The Crunchy Frog? Solution.

    We use the addition principle to show that there are \(3+4=7\) ways to choose your appetizer. Next, we choose one of 7 entrees. By the product principle, the total number of ways to order our meal is \(7 \times 7 = 49\text{.}\)

  2. At The Grey Duck, you get a choice of soup and a choice of salad with your entree. How many different meals can I order at The Grey Duck? Solution.

    We are ordering a 3-course meal. So we use the product principle twice to find that the total number of possible meals is \(3 \times 4 \times 7 = 84\text{.}\)

  3. I go to The Loon and Spoon for special occasions because they have 5 desserts. At this restaurant, an entree comes with your choice of 2 out of 3 of: soup, salad and dessert. (You are limited to at most one from each category: you cannot order 2 desserts!). How many different meals can I order at The Loon and Spoon? Solution.

    Okay, this one is more complicated than the others. But we can combine the product and addition principles to deal with choosing 2 out of the 3 choices. Let \(A\) be the set of soups, \(B\) the set of salads and \(C\) the set of desserts. Therefore, \(|A|=3\text{,}\) \(|B|=4|\) and \(|C|=5\text{.}\) Choosing 2 out of 3 of these means choosing one element from the set

    \begin{equation*} (A \times B) \cup (A \times C) \cup (B \times C). \end{equation*}

    Here, we have \(|A \times B|=12\) and \(|A \times C| = 15\) and \(|B \times C| = 20\text{,}\) all by the product principle. We then use the addition principle because these cartesian products are all disjoint. The number of ways to choose 2 out of 3 of these courses is \(12 + 15 + 20 =47\text{.}\)

    Next, we must choose our entree (7 choices), so the total number of meals that we can order is \(47 \times 7 = 329\text{.}\)

3. Subtraction Principle.

Recall that subset \(B\) of a set \(A\) is a subcollection of the elements of \(A\text{.}\) For example, the the set \(B= \{ 1, 3, 5 \}\) is a subset of \(A = \{ 1, 2, 3,4,5\}\text{.}\) Meanwhile, \(C = \{ 2, 4, 6 \}\) is not a subset of \(A\) since \(6 \notin A\text{.}\) We write \(B \subset A\) when \(B\) is a subset of \(A\text{.}\) Suppose that \(B \subset A\text{.}\) Formulate a natural subtraction principle for the size of \(A \backslash B\text{.}\) Solution.

The Subtraction Principle: Suppose that \(B \subset A\text{.}\) Then \(| A \backslash B| = |A| - |B|\text{.}\)

4. Passwords.

A computer system requires an alphanumeric (letters and numbers) password of length 8. At least one of these characters must be a number. Use your Subtraction Principle to count the number of passwords. Solution.

Let \(A\) be the set of all alphanumeric passwords of length 8, with no further restrictions. Clearly, \(|A_8| = (36)^8\) by the product principle. Let \(B\) be the subset of all "bad" passwords. Namely, the passwords that have no numbers. We have \(|B|= (26)^8\text{.}\) Therefore the set of all good passwords is \(A \backslash B\text{,}\) which has size \(36^8 - 26^8\text{.}\)