# The Multiplication Principle

The multiplication Principle
10.7
We now have the language that allows us to describe the objects that you are going to count, sequences, collections, sharings, compositions, permutations, sets. But how to count them, well, we will refer to two precise basic principles of counting. The first one is the so-called multiplication principle. It can be applied when the elements of a set X can be obtained through a sequence of steps. Let us say, K steps.
58.4
We assume that at the first step, we have a certain amount of partial outcomes. Let us call it M1 possibilities for the first outcome. For each of these outcomes, assume that at the second step, there is a fixed amount of possible outcomes. Let us call it M2, and this for every step up to the last one. But also, we require that from the element of X that is obtaining this way, we can uniquely determine the partial outcomes of step one, step two, step K. Equivalently, we require that different paths give different final outcomes. Well, if these assumptions are satisfied, then X as a number of elements equal to the product of the numbers, and one, and two, and K.
126
It is very important to check the fact that from the final outcome, so you look at the final outcome that is the element of the set X that you can say exactly what happened at step one, step two, step K. Forgetting this condition is the first source of errors in combinatorics, and we’ll see soon some examples. Let us prove the multiplication principle in the case of two steps.
157.7
Well, the fact that from the final outcome of X, we can uniquely recover the partial outcomes of steps one and two implies that there is a one to one correspondence between X and the pairs X1, X2, where X1 is an outcome of step one, and correspondingly to X1, X2 is an outcome of step two. Let us describe the possible pairs that we can obtain in such a way. Well, let us call A1 and one the outcomes of step one.
191.3
If we choose A1, we have M2 possible outcomes for the step two, and the same for A2, A3, and A1. Globally, we have M1 times M2. Because M2 plus plus plus M2 M1 times and 1 times M2 possible outcomes, so M1 times M2 elements of the set X. As an application of the multiplication principle, it turns out that the number of elements of the calculation product of K finance sets is the product of their elements. Let’s see why. Well, we can write the elements of the calculation product as a sequence X1 XK and form the sequence in K steps.
252
In the first, which is X1, the first element of the sequence, we have as many choices as are the elements of X1 up to step K, where we choose XK. And we have as many choices as every elements of XK. Notice, also, that from the final outcome, which is a sequence, X1, the first term, so X1 is the first step. X2 is the second term, so X2 is the outcome of the second step. And XK is the last term, so it is the outcome of step K. So we can apply the multiplication principle, which is the result.
296.5
As an example, let us count the number of ways in which we can choose a president and a vice president from a group of 15 people. While we can do it in two steps in the first step, which is the president, we have 15 choices. And in the second, which is the vice president. Also, from the final outcome, president, vice president, we know who was chosen as step one, the president, and who was chosen the step two, the vice president. So we can apply the multiplication principle, and this gives us 15 times 14 possible choices. Now, let us warn you that a bad use of the multiplication principle is the first source of error in combinatorics.
343.2
Often, if you don’t check the fact that from the final outcome, you can recover uniquely the partial outcomes, well, you may count more elements than what are the elements of the set that you are considering. Let us look at the following example. We want to choose two people from three in a group of three people. Well, clearly, we have three possible sets of two elements among three. If people are named A, B, C, we have a AB, BC, or AC. If we do it in two steps and we choose a first element, a first element of the committee of two people, we have three choices for the first person.
393.9
And once we have chosen the first person, we have two choices for the second. So if we apply the multiplication principle, we get six possibilities instead of three. Why? Well, the fact is that from the final outcome, which is a set of two people, we cannot say who was chosen in the first step and who was chosen the second step. So the multiplication principle cannot be applied in this situation. Let’s see another example of a bad use of the multiplication principle. We have three people, two women and one man. And we want to form a committee with two people. One of which is a woman, so let us call W1, W2, the two women and the man.
448.6
Clearly, we have three possible choices, W1, W2, W1M, and W2M. Actually, every set with two people contains one woman. You mentioned we want to form the committee with the multiplication principle in two steps. First, which was a woman among the two, so we have two choices. Then we choose the other person. We have two choices. So if one applies the multiplication principle, we get four possible choices. But actually, there are no four groups of two people among three people. So why do we get four instead of three? Well, from the final outcome, we cannot say what happened in the first step or in the second step. For instance, consider the set of the two women.
510.7
Who was chosen in the first step, and who was chosen in the second step?

We are already familiar wit sequences, sets, collections. How do we count them? We see here one of the most powerful tools in combinatorics: the Multiplication Principle. Be careful: its misuse is at the same time the first source of errors!