Tutorial: Decision algorithms: The addition and multiplication principles
(This topic is also in Section 6.3 in Finite Mathematics or Section 7.3 in Finite Mathematics and Applied Calculus) I don't like this new tutorial. Take me back to the old version of this tutorial!
Addition and multiplication principles
Let's start with a simple scenario:
%%Q You would like to see either a scifi or a horror movie. You walk into the movie theater and find that there are 3 scifi movies and 5 horror movies to choose from. How many different options do you have?%%A Because there are 3 scifi movies and 5 horror movies, you have $3 + 5 = 8$ to choose from. This scenario illustrates the following general principle:
Addition principle
When choosing among $r$ alternatives whose outcomes are all different, if:
When choosing among $r$ alternatives whose outcomes are all different, if:

Alternative 1 has $n_1$ possible outcomes,
Alternative 2 has $n_2$ possible outcomes,
...
Alternative $r$ has $n_r$ possible outcomes,
%%Example
In the scenario above, our decision on which movie to see is based on the following two alternatives:
In the scenario above, our decision on which movie to see is based on the following two alternatives:

Alternative 1 Choose a scifi movie : 3 outcomes,
Alternative 2 Choose a horror movie : 5 outcomes.
%%Q What does this have to do with sets?
%%A Good question! When we talk about the number of possible outcomes resulting from making decisions, we are really talking about the number of elements in the resulting set of outcomes; in other words, the cardinality of the resulting set of outcomes. %%Q In the %%prevsectut there are lots of rules for calculating cardinality. Is the addition principle some kind of new rule we should add to the list?
%%A No. Think about the addition principle in terms of cardinalities: If the set of outcomes of the first alternative is $A$ and set of outcomes of the second alternative is $B$, then the combined set of outcomes from both alternatives is their union $A \cup B$. As we are insisting that no two alternatives have any outcomes in common, we are really insisting that here, $A$ and $B$ are disjoint, and so, by the rule for the cardinality of a union in the %%prevsectut,
%%A Good question! When we talk about the number of possible outcomes resulting from making decisions, we are really talking about the number of elements in the resulting set of outcomes; in other words, the cardinality of the resulting set of outcomes. %%Q In the %%prevsectut there are lots of rules for calculating cardinality. Is the addition principle some kind of new rule we should add to the list?
%%A No. Think about the addition principle in terms of cardinalities: If the set of outcomes of the first alternative is $A$ and set of outcomes of the second alternative is $B$, then the combined set of outcomes from both alternatives is their union $A \cup B$. As we are insisting that no two alternatives have any outcomes in common, we are really insisting that here, $A$ and $B$ are disjoint, and so, by the rule for the cardinality of a union in the %%prevsectut,
$n(A \cup B) = n(A) + n(B) \qquad$ \t Just add the cardinalities if the sets are disjoint.
%%Q Now how many different options do you have?
%%AFor each of the three 3 scifi movies, there are two times, giving 6 possibilities, and for each of these six choices, there are two auditoriums, giving a total of 12 possibilities. Notice that this time, we needed to make a sequence of three decisions: First decide on a movie, then a time, and finally a type of auditorium. This scenario illustrates the following general principle.
Multiplication principle
When making a sequence of choices with $r$ steps, if:
When making a sequence of choices with $r$ steps, if:
 #[Step 1 has $n_1$ possible outcomes,][Paso 1 tiene $n_1$ resultados posibles,]#
#[Step 2 has $n_2$ possible outcomes,][Paso 2 tiene $n_2$ resultados posibles,]#
...
#[Step $r$ has $n_r$ possible outcomes][Paso $r$ tiene $n_r$ resultados posibles,]#
%%Example
Gift pen sets come in three presentations: fancy, semifancy, and plain. Each presentation includes either a fountain pen or a ballpoint pen, and comes in four colors. To decide on a pen set for an acquantiance, you make a sequence of three decisions:
Gift pen sets come in three presentations: fancy, semifancy, and plain. Each presentation includes either a fountain pen or a ballpoint pen, and comes in four colors. To decide on a pen set for an acquantiance, you make a sequence of three decisions:

Step 1: Choose a presentation: 3 possible outcomes
Step 2: Choose a type of pen: 2 possible outcomes
Step 3: Choose a color: 4 possible outcomes
%%Q What does this tule have to do with sets?
%%A As we said above, we are calculating the cardinality of the resulting set of outcomes. %%Q For the addition principle we used the rule for the cardinality of a (disjoint) union. Which rule do we need here and why?
%%A If the set of outcomes of the first step is $A$ and set of outcomes of the second step is $B$, then the set of outcomes resulting from both steps in succession is a choice of an element $a$ of $A$ followed by a choice of an element $b$ of $B$; so we are really choosing a pair of elements $(a, b)$ with $a \in A$ and $b \in B;$ in other word, an element of the Cartesian product $A \times B$, and so, by the rule for the cardinality of a Cartesian product in the %%prevsectut,
%%A As we said above, we are calculating the cardinality of the resulting set of outcomes. %%Q For the addition principle we used the rule for the cardinality of a (disjoint) union. Which rule do we need here and why?
%%A If the set of outcomes of the first step is $A$ and set of outcomes of the second step is $B$, then the set of outcomes resulting from both steps in succession is a choice of an element $a$ of $A$ followed by a choice of an element $b$ of $B$; so we are really choosing a pair of elements $(a, b)$ with $a \in A$ and $b \in B;$ in other word, an element of the Cartesian product $A \times B$, and so, by the rule for the cardinality of a Cartesian product in the %%prevsectut,
$n(A \times B) = n(A)n(B) \qquad$ \t Multiply the cardinalities.
Combining the addition and multiplication principles
Now let's look at a situation that calls for combining both principles. The following is similar to Example 1 in Finite Mathematics:
We can think of each of the examples we have looked at so far as determining the number of outcomes of some activity, like deciding on a pen set, choosing an entree, filling out a multilechoice answer sheet, or ordering refreshements. In each case, we needed to make a sequence of decisions in order to determine the outcome, and the sequence of decisions we wrote down in each case is called a decision algorithm.
Decision algorithms
Decision algorithm
A decision algorithm is a systematic list of decisions we need to make in order to completely determine an outcome of some activity. We can use a decision algorithm to determine the number of possible outcomes by applying the addition and multiplcation principles to the decision algorithm.
In short:
%%A What it means for a decision algorithm to be valid is that making different choices must always result in a different outcome. For instance, if you look at the decision algorithm we wrote down to decide on a gift pen set, making different decisions in any of the three steps would result in a different gift.
A decision algorithm is a systematic list of decisions we need to make in order to completely determine an outcome of some activity. We can use a decision algorithm to determine the number of possible outcomes by applying the addition and multiplcation principles to the decision algorithm.
In short:
To count the number of possible outcomes of some activity, come up with a valid* decision algorithm to determine the outome by systematically listing the decisions to be made at each stage, and then apply the addition and multiplication principles.
%%Q Wait a minute! what is all this about a "valid" decision algorithm? %%A What it means for a decision algorithm to be valid is that making different choices must always result in a different outcome. For instance, if you look at the decision algorithm we wrote down to decide on a gift pen set, making different decisions in any of the three steps would result in a different gift.
%%Examples
1. You are the coach of the Enormous State U Blastball team. Your team is to have four players: a striker, two blasters, and a blocker. You have five possible players to choose from to make up the team. Following are two decision algorithms; one are valid and one is invalid. In the first algorithm, you pick players for the five positions onbyone to form the team. In the second, you instead fill the three positions onebyone:
1. You are the coach of the Enormous State U Blastball team. Your team is to have four players: a striker, two blasters, and a blocker. You have five possible players to choose from to make up the team. Following are two decision algorithms; one are valid and one is invalid. In the first algorithm, you pick players for the five positions onbyone to form the team. In the second, you instead fill the three positions onebyone:
\t
Step 2: Pick the first blaster: 4 choices
Step 3: Pick the second blaster: 3 choices
Step 4: Pick the blocker: 2 choices
Total: 5×4×3×2 = 120 possible teams
\t
Step 2: Pick the blocker: 4 choices
Step 3: Pick two of the remaining three to be the blasters: 3 choices
(Choose which of the three to leave out.)
Total: 5×4×3 = 60 possible teams
Although each of these algorithms leads to a blastball team, Algorithm 1 is not valid for counting the number of possible teams you can make. Why? Suppose that Joaquim and Matilda are two players. Then, if you choose Joaquim in Step 2 and Matilda in Step 3, you end up wit the same two blasters as you would by choosing Matilda in Step 2 and Joaquim in Step 3. Thus switching your decisions in Steps 2 and 3 results in the same outcome (the same team), and so the Algorithm 1 is not valid.On the other hand, if you make changes any of your decisions in Algorithm 2, the resulting team will be different (think about why). Thus, Algorithm 2 is valid.
Decision algorithm 1
Step 1: Pick the striker: 5 choices Step 2: Pick the first blaster: 4 choices
Step 3: Pick the second blaster: 3 choices
Step 4: Pick the blocker: 2 choices
Total: 5×4×3×2 = 120 possible teams
Decision algorithm 2
Step 1: Pick the striker: 5 choices Step 2: Pick the blocker: 4 choices
Step 3: Pick two of the remaining three to be the blasters: 3 choices
(Choose which of the three to leave out.)
Total: 5×4×3 = 60 possible teams
2. You have four cards spread in front of you; each with a single digit printed on it: Two of them have a "1", one has a "2", and one has a "3". You want to know how many different 4digit sequences you can make by arranging the cards in different orders.Following are three decision algorithms; two are valid and one is invalid. In the first algorithm, we pick the four cards onebyone to form the sequence. In the second and third, we instead think of placing the four cards in four empty slots in order to obtain the sequence:
\t
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4digit sequences][secuencias de 4 dígitos]#
\t
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 1][Algoritmo de decisión 1]#
#[Step 1: Pick the first card: 4 choices][Paso 1: Escoje la primera carta: 4 opciones]#
#[Step 2: Pick the second card: 3 choices][Paso 2: Escoje la segunda carta: 3 opciones]#
#[Step 3: Pick the third card: 2 choices][Paso 3: Escoje la tercera carta: 2 opciones]#
#[Step 4: Pick the fourth card: 1 choice][Paso 4: Escoje la cuarta carta: 1 opción]#
Total: 4×3×2×1 = 24 #[4digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 2][Algoritmo de decisión 2]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para el "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para el "3": 3 opciones]#
#[Step 3: Pick a pair of slots for the "1"s: 1 choice][Paso 3: Escoje un par de espacios para los "1": 1 opción]#
(#[Only a single pair of slots remains for Step 3.][Solo queda uno solo par de espacios para paso 3.]#)
Total: 4×3×1 = 12 #[4digit sequences][secuencias de 4 dígitos]#
#[Decision algorithm 3][Algoritmo de decisión 3]#
#[Step 1: Pick a slot for the "2": 4 choices][Paso 1: Escoje un espacio para la "2": 4 opciones]#
#[Step 2: Pick a slot for the "3": 3 choices][Paso 2: Escoje un espacio para la "3": 3 opciones]#
(#[No more steps necessary: the "1"s must goes in the remaining 2 slots.][No se necesitan más pasos: los "1" debe ir en las 2 ranuras restantes.]#)
Total: 4×3 = 12 #[4digit sequences][secuencias de 4 dígitos]#
#[Although each of these algorithms leads to a 4digit sequence, Algorithm 1 is not valid for counting the number of possible 4digit sequences. Why? Because, for instance, we can use Algorithm 1 get the same sequence "3121" by making different decisions as follows:][Aunque cada uno de estos algoritmos conduce a una secuencia de 4 dígitos, el Algoritmo 1 no es válido para contar el número de posibles secuencias de 4 dígitos. ¿Por qué? Porque, por ejemplo, podemos usar el Algoritmo 1 para obtener la misma secuencia "3121" al hacer diferentes decisiones como sigue:]#
\t
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
\t #[Step 2: Pick the second card: Choose the leftmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la izquierda.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 1: Pick the first card: Choose the "3".][Paso 1: Escoje la primera carta: Escoje el "3".]#
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
#[Step 2: Pick the second card: Choose the rightmost "1".][Paso 2: Escoje la segunda carta: Escoje elige el "1" más a la derecha.]#
#[Step 3: Pick the third card: Choose the "2".][Paso 3: Escoje la tercera carta: Escoje el "2".]#
#[Step 4: Pick the fourth card: Choose the remaining "1".][Paso 4: Escoje la cuarta carta: Elije el "1" restante.]#
#[Result][Resltado]#: 3121
Now try some of the exercises in Section 6.3 in Finite Mathematics or Section 7.3 in Finite Mathematics and Applied Calculus.
Last Updated: July 2023
Copyright © 2022 Stefan Waner and Steven R. Costenoble
Copyright © 2022 Stefan Waner and Steven R. Costenoble