Skip to main content

Section 3.2 Probability, Permutations and Combinations

Before we can start calculating the probability that two letters picked at random from a ciphertext are identical we should learn how to calculate probabilities in general!

Definition 3.2.1.

The probability of an event occurring is \(\frac{r}{n}\) where \(n\) is the total number of possible outcomes and the event can happen in \(r\) equally likely ways.

Example 3.2.2.

Given the five letters, A, B, C, D, E. If we pick one letter at random what is the probability that it is an A? a vowel? a consonant?

  • Since there is only one A, the probability of picking an A is 1/5.

  • Since there are two vowels, the probability of picking a vowel is 2/5.

  • Since there are three consonants, the probability of picking a consonant is 3/5. Note there is another way to calculate this. Since the only way a letter can be a consonant is if it is not a vowel, we could calculuate this as the probability of not getting a vowel. The probability of not getting a vowel is 1-2/5=3/5.

Example 3.2.4.

Suppose we pick two letters at random from the set A, B, C, D, E. What is the probability that both of them are vowels?

There are different ways to think about this depending on our assumptions. Are we picking one letter and replacing it so we may pick the same letter both times, or are we picking both letters at the same time? If we are picking both letters at the same time do we care about the order in which we got the letters or do we not care about the order? Let's look at all three of those cases.

  1. Case 1: Replacement. We pick one letter and return it so that picking exactly the same letter twice is possible. In this case we may pick AA, AE, EA, or EE to pick two vowels. There are 25 ways to pick any two letters from this set, namely AA, AB, AC, AD, AE, BA, BB, BC, BD, BE, CA, CB, CC, CD, CE, DA, DB, DC, DD, DE, EA, EB, EC, ED, EE. Thus, the probability is 4/25.

  2. Case 2: No replacement and order does matter. In this case, we pick both letters at the same time. Thus, we may not pick the exact same letter twice. The possible ways to pick two vowels are AE or EA. There are 20 ways to pick any two letters from this set, namely, AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED. Thus, the probability is 2/20.

  3. Case 3: No replacement and order does not matter. In this case, there is only one way to pick two vowels namely A and E. There are now only 10 ways to pick any two letters from this set, namely, AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Thus, the probability is 1/10. In this case, we get the same probability as in Case 2, but that will not usually happen.

Let's talk about how to make the calculation for the denominator in each of these three cases.

For Case 1, we have a set of five letters and want to pick two of them allowing replacement. In this case, there are 5 choices for the first letter and five choices for the second letter, so the total number of ways to choose two letters from a set of 5 allowing replacement is

\begin{equation*} 5 \times 5 = 25. \end{equation*}

This same calculation holds in general.

For Case 2 we have a set of five letters and want to pick two of them; we care about order but do not allow replacement. In this case, there are five choices of letters to pick for the first letter, but only four choices of letter to pick for the second letter, since we cannot pick whatever letter we picked first. Thus the total number of ways to choose two letters from a set of 5 where order matters but replacement is not allowed is

\begin{equation*} 5 \times 4 = 20. \end{equation*}

This type of computation is referred to as a permutation.

Definition 3.2.6.

A permutation \(P(n,r)=\) is the number of ways to arrange \(r\) objects from a set of \(n\text{.}\) (Order matters.)

Note that order matters for a permutation because we are arranging the objects. In general, to compute \(P(n,r)\) there are \(n\) ways to pick the first object, then \(n-1\) ways to pick the second object and so on down to \(n-r+1\) ways to pick the \(r\)th object. We can rewrite this using factorials to get:

For Case 3 we have a set of five letters and want to pick two of them; we do not care about order and do not allow replacement. In this case our calculation of \(5 \times 4 = 20 \) is much too big and overcounts many pairs of letters. For example, the the letters A and B, it counts both AB and BA separately. In fact, it double counts for every pair of letters in exactly the same way. Thus the total number of ways to choose two letters from a set of 5 where order does not matter and replacement is not allowed is

\begin{equation*} \frac{5 \times 4}{2} = 10. \end{equation*}

This is referred to as a combination.

Definition 3.2.8.

A combination \(C(n,r)=\) is the number of ways to choose \(r\) objects from a set of \(n\) objects. (Order does not matter.)

Note that order does not matter for a combination because we are choosing objects but not arranging them. In this case, the permutation has overcounted by all the possible orderings of \(r\) objects. Thus we need to divide the permutation by \(r!\text{.}\)

Let's look at an example where the ideas are a little more complicated.

Example 3.2.10.

We have a bucket of 20 letters. These letters include A, B, C and are either red or blue. There are 4 red As, 6 blue As, 4 red Bs, 3 blue Bs, 1 red Cs and 2 blue Cs. In this case, we do not care about order when we are picking letters.

  1. Suppose we pick one letter from the bucket.

    1. What is the probability of picking one A or one B?

    2. What is the probability of picking one A or one red letter?

  2. Suppose we pick two letters from this bucket at the same time.

    1. What is the probability of picking one A and one B?

    2. What is the probability that both are the same letter? That is, what is the probability that we pick AA or BB or CC?

    3. What is the probability that at least one letter is blue?

    4. What is the probability that one letter is A and the other letter is red.

Solution

  1. There are \(C(20,1)=20\) ways to pick one letter from the bucket.

    1. There are \(C(10,1)=10\) ways to pick an A and there are \(C(7,1)=7\) ways to pick a B. Since picking an A or picking a B are disjoint events, the probability is \(\frac{C(10,1)+C(7,1)}{20}=\frac{17}{20}\text{.}\)

    2. In this case, there are 10 letter As and 9 red letters, but we cannot add probabilities because there is overlap between A letters and red letters. We need to create multiple cases to eliminate any overlap and avoid double counting the four red As. We could count the number of ways to pick a blue A or pick a red letter instead. This covers all the same cases without double counting. The probability is \(\frac{C(6,1)+C(9,1)}{20}=\frac{15}{20}\text{.}\)

  2. There are \(C(20,2)=190\) ways to pick two letters from the bucket.

    1. Since there is no overlap in picking an A or picking a B, the probability is \(\frac{C(10,1)C(7,1)}{190}=\frac{70}{190}\text{.}\)

    2. Again, there is no overlap in picking two As, two Bs, or two Cs.The probability is \(\frac{C(10,2)+C(7,2)+C(3,2)}{190}=\frac{69}{190}\text{.}\)

    3. There are two ways that at least one letter is blue: either exactly one letter is blue or both letters are blue. We could compute the probably of each of these and add them since they are disjoint cases, but its easier to compute the opposite event. That is, what is the probability that we don't get any blue letters? This means both letters must be red so the probability is\(\frac{C(9,2)}{C(20,2)}\text{.}\) Since this is the event we don't want, the probability of at least one blue is \(1-\frac{C(9,2)}{C(20,2)}=\frac{154}{190}\text{.}\)

    4. There is overlap in the letters that are As and the red letters, so we have to separate into cases to avoid the overlap. We first separate based on whether the A is red or blue. However, if the A is red then we also have separate based on whether the other letter is a red A, so that there are three cases for this example.

      • Case 1: Both letters are red As. There are \(C(4,2)=6\) ways to pick two red As.

      • Case 2: One letter is a red A and the second letter is a red B or C. There are \(C(4,1)*C(5,1)=20\) ways to pick this.

      • Case 3: One letter is a blue A and the second letter is red (any of A, B, C). There are \(C(6,1)*C(9,1)=54\) ways to pick this

      Thus, the probability is \(\frac{6+20+54}{190}=\frac{80}{190}\text{.}\)

Both Investigation: Probability Practice and Example 3.2.10 should have raised some important questions.

  1. In some cases we added different probabilities and in some cases we multiplied different probabilities? In general, when do we multiply and when do we add?
  2. For the probability about one letter being A or the other letter being blue, we had to be careful about splitting it up into separate cases. When do we have to worry about that in general?
  3. When is it better to calculate the opposite probability?

For the first question, if the two outcomes are disjoint (meaning they can't both happen at the same time) then we can add the probabilities. Often, this corresponds to a probability involving “or”. For example, when we are picking two letters from the bucket, picking AA or BB, are disjoint events. We can't pick AA and BB at the same time.

For the second question, if the two outcomes are independent from each other and we need both of them to occur, then we multiply probabilities. For example, when picking one letter as an A and the other letter as a B we multiplied the probabilities because picking an A for one letter does not impact the ways we can choose B as a second letter. These events are independent. Often, this corresponds to a probability involving “and”. However, this is not always the case. The events may not be independent such as in the example of picking one A and the other letter being red. It is also possible that “and” is used in a different way. For the probability of picking one letter that is both an A and red, we would not multiply the number of As times the number of red letters.

The last question doesn't have an easy answer. You'll just have to think about it for each problem. Sometimes it is easier to compute the opposite event, \(p\text{,}\) and use \(1-p\) for the probability of the desired event. This also points out that probabilities should be between 0 and 1. If a probability is 0 then that event will never happen and if a probability is 1 then that event is guaranteed to happen.