Skip to main content

Chapter 18 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?

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?

  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?

  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?

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{.}\)

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.