The Multiplication Principle

Printer-friendly versionPrinter-friendly version

Example

Dr. Roll Toss wants to calculate the probability that he will get:

a 6  6 on a die and a head penny

when he rolls a fair six-sided die and tosses a fair coin.  Because his die is fair, he has an equally likely chance of getting any of the numbers 1, 2, 3, 4, 5, or 6. Similarly, because his coin is fair, he has an equally likely chance of getting a head or a tail.  Therefore, he can use the classical approach of assigning probability to his event of interest.  The probability of his event A, say, is:  

\(P(A)=\dfrac{N(A)}{N(S)}\)

where N(A) is the number of ways that he can get a 6 and a head, and N(S) is the number of all of the possible outcomes of his rolls and tosses.  There is of course only one possible way of getting a 6 and a head.  Therefore, N(A) is simply 1.  To determine N(S), he could enumerate all of the possible outcomes:

S = {1H, 1T, 2H, 2T, ...}

and then count them up.  Alternatively, he could use what is called the Multiplication Principle and recognize that for each of the 2 possible outcomes of a tossing a coin, there are exactly 6 possible outcomes of rolling a die. Therefore, there must be 6 × 2 = 12 possible outcomes in the sample space.  The following animation illustrates the Multiplication Principle in action for Dr. Roll Toss' problem:

In summary, then the probability of interest here is P(A) = 1/12 or 0.083.  Of course, this example in itself is not particularly motivating. The main takeaway point should be that the Multiplication Principle exists and can be extremely useful for determining the number of outcomes of an experiment (or procedure), especially in situations when enumerating all of the possible outcomes of an experiment (procedure) is time- and/or cost-prohibitive. Let's generalize the principle.

The Multiplication Principle. If there are:

  • n1 outcomes of a random experiment E1
  • n2 outcomes of a random experiment E2
  • ... and ...
  • nm outcomes of a random experiment Em

then there are n1 × n2 × ... × nm outcomes of the composite experiment E1E2 ... Em.

The hardest part of using the Multiplication Principle is determining, ni, the number of possible outcomes for each random experiment (procedure) performed.  You'll want to pay particular attention to:

  • whether replication is permitted
  • whether other restrictions exist

Let's take a look at another example.

Example

How many possible license plates could be stamped if each license plate were required to have exactly 3 letters and 4 numbers?

license plate

Solution. Imagine trying to solve this problem by enumerating each of the possible license plates:  AAA1111, AAA1112, AAA1113, ... you get the idea!  The Multiplication Principle makes the solution straightforward.  If you think of stamping the license plate as filling the first three positions with one of 26 possible letters and the last four positions with one of 10 possible digits:

enumeration of letters and numbers

the Multiplication Principle tells us that there are: 

multiplication

Again, that is:

(26 × 26 × 26) × (10 × 10 × 10 × 10)

or 175,760,000 possible license plates.  That's a lot of license plates!  If you're hoping for one particular license plate, your chance (1 divided by 175,760,000) of getting it are practically nil. 

Now, how many possible license plates could be stamped if each license plate were required to have 3 unique letters and 4 unique numbers?

Solution. In this case, the key is to recognize that the replication of numbers is not permitted. There are still 26 possibilities for the first letter position.  Suppose the first letter is an A. Then, since the second letter can't also be an A, there are only 25 possibilities for the second letter position. Now suppose the second letter is, oh let's say, a B.  Then, since the third letter can't be either an A or a B, there are only 24 possibilities for the third letter position. Similar logic applies for the number positions.  There are 10 possibilities for the first number position. Then, supposing the first number is a zero, there are only 9 possibilities for the second number position, because the second number can't also be a zero. Similarly, supposing the second number is a one, there are only 8 possibilities for the third number position. And, supposing the third number is a two, there are 7 possibilities for the last number position:

enumeration

Therefore, the Multiplication Principle tells us that in this case there are 78,624,000 possible license plates:

multiplication

That's still a lot of license plates!

Example

Let's take a look at one last example.   How many subsets are possible out of a set of 10 elements?

Solution. Let's suppose that the ten elements are the letters A through J:

A,  B , C,  D,  E,  F,  G,  H,  I,  J

Well, there are 10 subsets consisting of only one element: {A}, {B}, ..., and {J}.  If you're patient, you can determine that there are 45 subsets consisting of two elements: {AB}, {AC}, {AD}, ..., {IJ}.  If you're nuts and don't mind tedious work, you can determine... oh, never mind! Let's use the Multiplication Principle to tackle this problem a different way.  Rather than laboriously working through and counting all of the possible subsets, we could think of each element as something that could either get chosen or not get chosen to be in a subset. That is, A is either chosen or not... that's two possibilities.  B is either chosen or not... that's two possibilities.  C is either chosen or not... that's two possibilities. And so on. Thinking of the problem in this way, the Multiplication Principle then readily tells us that there are:

(2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2)

or 210 = 1,024 possible subsets.  I personally would not have wanted to solve this problem by having to enumerate and count each of the possible subsets. Incidentally, we'll see many more problems similar to this one here when we investigate the binomial distribution later in the course.