Basics of Combinations / Probability
Click here for definitions of terms
Combinations, Permutations, and Probability often go together, because the former 2 are often used in the calculation of probability. As a simple example, if we want to calculate the probability that one roll of two dice will yield a 5, then we need to calculate the total number of possible combinations of one roll of the dice, as well as the number of ways 5 could come up. But let’s start by defining some terms.
Permutations
Permutations of a set of objects are different arrangements of the objects where order is important. For example, {1, 2, 3} can be ordered in 6 different ways: 123, 132, 213, 231, 312, 321.
The number of permutations of a set of n objects is n! (n factorial). This can be seen most easily if you think of an arrangement of n things as a placement of them into a set of n slots. There are n possibilities for the first slot. For each of these n possibilities, there are n-1 possibilities for the second slot, and for each of these there are n-2 for the third, etc. Altogether then there are
n × n-1 × n-2 × … × 2 × 1 = n!
different arrangements or permutations of n things.
As an example, if we have 5 different books on a bookshelf, how many different ways could we arrange them? Well, we have 5 choices for the first book, then 4 choices for the second book, etc. So the answer is
5! = 5 × 4 × 3 × 2 × 1 = 120.
Sometimes we want to select a few things from a set and then arrange those things we’ve selected. Suppose we want to choose 2 books from a set of 5 to put on a shelf. How many different possible arrangements are there? It’s easy to see that there are 5 choices for the first book, and then 4 choices for the second. So altogether there are 5 × 4 = 20 different possible arrangements of 2 books selected from a set of 5.
In general, the formula for the number of permutations of n things taken p at a time is
\(\begin{align} \frac {n!}{(n-p)!}\end{align}\)
Therefore, if n is 5, and p is 2, this formula works out to
\(\begin{align} \frac {5!}{(5-2)!}\end{align}\) = \(\begin{align} \frac {5!}{3!}\end{align}\) = \(\begin{align} 5 \times 4 = 20\end{align}\)
Notice that if we want to arrange the entire set of n things in order, then the number of permutations is of n things taken n at a time:
\(\begin{align} \frac {n!}{(n-n)!}\end{align}\)
which is equal to
\(\begin{align} \frac {n!}{0!}\end{align}\)
and since 0! is equal to 1, then the final formula for the number of permutations of n things is
\(\begin{align} n!\end{align}\)
as we showed above.
Let’s look at a permutation problem where we have multiple instances of the same object.
How many ways are there of arranging the letters in MISSISSIPPI?
This word contains 4 I’s, 4 S’s, and 2 P’s. Notice that if we switch the positions of any two of these the letters are in exactly the same order, and so switching positions of the different occurrences of the same letter does not yield a new permutation. So, how do we calculate the total number of permutations? The key is to approach the problem in two steps. First, pretend that all 11 letters are different. Then the number of permutations of 11 letters is
11!
Now the number of permutations of 4 I’s is 4!, 4 S’s is 4!, and 2 P’s is 2! Since none of these permutations is a real permutation of MISSISSIPPI, then we need to divide the original 11! by each of these:
\(\begin{align} \frac {11!}{4!4!2!}\end{align}\) = \(\begin{align} \frac {11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5}{4!2!}\end{align}\) = \(\begin{align} 11 \times 10 \times 9 \times 7 \times 5\end{align}\) = \(\begin{align} 34,650\end{align}\)
Notice that we canceled out like values in the numerator and denominator. This made the final computation easier.
Combinations
Combinations are groupings of a set of objects without regard to order. For example, there are 7 different combinations of the elements in the set {1, 2, 3}: {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Notice that in all of these the order in which they are listed is not important. Thus, for example, the set {1, 2} is exactly the same set as {2, 1}. This is in contrast to permutations, where order is important.
There are 3 combinations of these elements if we take them just 2 at a time: {1, 2}, {1, 3}, {2, 3}. Another way of saying this is that the number of combinations of 3 things, taken 2 at a time, is 3. The number of combinations of n things taken p at a time is given by the formula
\(\begin{align} \frac {n!}{(n-p)!p!}\end{align}\)
\(\begin{align} n \choose p\end{align}\)
which is said, “n choose p.” If n is 3 and p is 2, then this formula becomes:
\(\begin{align} \frac {3!}{(3-2)!2!} = \frac {3!}{2!} = \frac {3 \times 2 \times 1}{2 \times 1} = 3\end{align}\)
Example: Suppose 3 people are to be selected at random from a group of 10 to form a committee to plan an activity for the group. How many different committees are possible? This is a typical application of the idea of combinations. In this case, it doesn’t matter what order we list committee members in. Thus, the committee George, Mary Ann, and Margaret is exactly the same committee as Margaret, George, and Mary Ann.
So, what’s the answer to the problem? We need to choose 3 people out of 10, so the formula called “10 choose 3” is the right formula. That is,
\(\begin{align} 10 \choose 3 \end{align}\) = \(\begin{align} \frac {10!}{(10-3)!3!} = \frac {10!}{7!3!} = \frac {10 \times 9 \times 8}{3 \times 2} = 120\end{align}\)
In other words, there are 120 different possibilities for committees of 3 chosen from a group of 10 candidates.
Example: Michael must take two courses from a group of 3 and two other courses from a group of 5 to complete his major. How many different possibilities are there for sets of courses he must take from these two groups? In this problem we seek two sets of combinations, and then we combine them to find the total number of combinations. Here are the first two sets:
\(\begin{align} 3 \choose 2 \end{align}\) = \(\begin{align} \frac {3!}{(3-2)!2!} = 3\end{align}\)
\(\begin{align} 5 \choose 2 \end{align}\) = \(\begin{align} \frac {5!}{(5-2)!2!} = 10\end{align}\)
That is, there are 3 possible choices of two courses from the first group and 10 possible choices of 2 courses from the second group. At this point we simply multiply these two numbers and get 30 possible choices of courses from the two groups.
Probability
In probability theory, an experiment is a procedure used to measure specific instances of outcomes of the experiment. For example, tossing a coin is an experiment, and its possible outcomes are heads (H) and tails (T). In the probability experiment of rolling a die, the possible outcomes are the numbers 1 – 6.
An event is a particular set of possible outcomes of a probability experiment. Example: A rolled die showing a number less than 3 is an event. The experiment is the rolling of the die. The set of possible outcomes is {1, 2, 3, 4, 5, 6}. The event of the die showing less than 3 in this example is the set {1, 2}.
A given experiment might involve multiple repetitions of the same procedure. For example, multiple coin tosses can be combined into a single experiment, as can multiple rolls of dice. If we flip a coin 3 times, then the possible outcomes are {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}. For this experiment, an event could be getting heads on the first toss. This event is equal to the set {HHH, HHT, HTH, HTT}.
The probability of an event is a measure of the likelihood that the event will happen. It’s typically computed as a fraction, with the number of possible outcomes of the event in the denominator, and the number of favorable outcomes in the numerator. That is, the probability of a given event is calculated using the basic formula:
\(\begin{align}probability = \frac {number\hspace{1mm} of\hspace{1mm} favorable\hspace{1mm} outcomes}{number\hspace{1mm} of\hspace{1mm} possible\hspace{1mm} outcomes}\end{align}\)
In general, this formula only holds if each outcome is as probable as every other outcome, or in other words if the outcomes are equally probable. If a coin is “fair,” then both heads and tails are equally probable. That is, the probability of heads is 1/2, and the probability of tails is 1/2. If each face of a 6-sided die is equally probable, then the probability of getting any particular number, 1-6, is always 1/6. In our discussion examples, we assume the outcomes are equally probable.
In the example above, if we roll a die and hope for a 1 or 2 to show, then there are 2 favorable outcomes, 1 and 2, and 6 possible outcomes. So the probability of getting a 1 or 2 is 2/6 = 1/3. As another example, if you randomly draw a card from a pack of 52 with 4 aces in it, the probability of drawing an ace is 4/52, or 1/13. The number of possible outcomes is 52, and the number of outcomes favorable to drawing an ace is 4.
Notice that the probability of an event is always a fraction between 0 and 1. This is because the number of favorable outcomes is always less than or equal to the number of possible outcomes. If an event is the empty set, then its probability is 0. If the event is the entire set of outcomes, then its probability is 1. If A is an event, then we will denote the probability of A by P(A). Therefore, if ∅ is the empty set, then P(∅) = 0, and if M is the set of possible outcomes, P(M) = 1.
Probabilities of Combined Events
Since events are sets, we can use the normal set operations on events and calculate the probabilities of the resulting sets. For example, suppose M is the set of all outcomes, as shown in the diagram. 
If A and B are events, then the sets created by these operations, A ∪ B (yellow and green, blue, and purple), A ∩ B (blue), A – B (yellow and green), and ¬ A (the complement of A – everything except the yellow, green, and blue), are also events, since they’re sets of outcomes. Additionally, if C ⊂ A, then C (green) is an event. We can calculate the following probabilities:
- P(A ∪ B) = P(A) + P(B) – P(A ∩ B)
- P(A – B) = P(A) – P(A ∩ B)
- P(¬A) = 1 – P(A)
- C ⊂ A implies P(C) ≤ P(A)
- P(∅) = 0
- P(M) = 1
Notice that if A and B are disjoint, then A ∩ B = ∅, so in that case formula 1 reduces to:
1´. P(A ∪ B) = P(A) + P(B)
Formula 3 can be derived by using formula 1´ and the facts that (1) A and ¬A are disjoint and (2) their union equals the entire set M, so
P(A) + P(¬A) = P(M) = 1
P(¬A) = 1 – P(A)
Here are a few examples. Assume we’re rolling a single die, so M = {1, 2, 3, 4, 5, 6}. Also, A = {1, 2, 3}, B = {3, 4, 5}, and C = {1, 2}. Therefore, P(A) = P(B) = 1/2, P(C) = 1/3, and P(A ∩ B) = 1/6. We have the following probabilities:
- P(A ∪ B) = P(A) + P(B) – P(A ∩ B) = 1/2 + 1/2 – 1/6 = 5/6 = P({1, 2, 3, 4, 5}), since A ∪ B = {1, 2, 3, 4, 5}.
- P(A – B) = P(A) – P(A ∩ B) = 1/2 – 1/6 = 1/3 = P({1, 2}), since A – B = {1, 2}.
- P(¬C) = 1 – P(C) = 1 – 1/3 = 2/3 = P({3, 4, 5, 6}), since ¬C = {3, 4, 5, 6}.
What about the probability of A ∩ B? Obviously, that’s an important probability, and if we know the number of elements in A ∩ B, and in M we can calculate it, as we did in the examples above, but otherwise we need to look at some other concepts to see how to derive it. We’ll explore these when we discuss conditional probability below (see formulas 8 and 9).
Conditional Probability and Independent Events
Conditional probability measures the probability of an event, given that another event has occurred. For example, suppose for the experiment of rolling a die we define 2 events as event A – getting an even number, which is the set {2, 4, 6} – and event B – getting a number above 3 {4, 5, 6}. Notice that the probability of each of these separately is 1/2.
Now let’s suppose we roll event A – that is, an even number shows. What’s the probability of event B, a number above 3, if we know that an even number has been rolled? We calculate easily that the probability of B in this case is the probability that we got a 4 or a 6, knowing that the roll was either 2, 4, or 6. That is, we have 2 out of 3 chances of B if A has occurred. Or, in other words, the probability of B given A is 2/3. (Reversing the roles of the two sets, we see that if B has occurred, then the probability that A has occurred is also 2/3.)
[As an aside, notice, in this example that P(A) = P(B) = 1/2, but P(A | B) = P(B | A) = 2/3. This shows that A and B are not independent events, as we’ll see below.]
Now, the only elements in B that are relevant in this calculation are those that are also in A, that is the elements in A ∩ B. Thus, this example suggests the general formula for conditional probability, which we give in two versions:
7. P(B | A) = P(A ∩ B) / P(A)
7´. P(A | B) = P(A ∩ B) / P(B)
The expression P(B | A) means the probability of B given A. Multiplying both sides of formula 7 by P(A), and reversing the two sides of the formula, we get a formula for the probability of the intersection of A and B, A ∩ B:
8. P(A ∩ B) = P(B | A) · P(A)
8´. P(A ∩ B) = P(A | B) · P(B)
These formulas, 7 and 8, are general formulas for conditional probability. They apply to all events A and B.
Two events are independent if the occurrence of one does not change the probability of the occurrence of the other. That is, if A and B are independent, then
P(A | B) = P(A)
P(B | A) = P(B)
So if A and B are independent events, we can modify formulas 8 and 8´ to get
9. P(A ∩ B) = P(A) · P(B)
In the previous example, we noted that sets A and B are not independent, because individually their probabilities are 1/2, but when we know A has occurred, then the probability of B goes to 2/3, and vice versa if we know B has occurred. But what are some examples of independent events?
Independent events do occur for example when a coin is flipped multiple times, or two dice are rolled. In the first case, it doesn’t matter how many times in a row we get tails, the probability that we’ll get heads on the next flip of the coin remains 1/2 (assuming the coin and the flipping process are truly fair and random). When we roll two dice, the fact that one die shows 4 has no influence on the other die. Its probability of showing any number between 1 and 6 remains 1/6.
Example 1: What is the probability that a roll of two dice will have a value of 5?
Solution: To get 5 from the two dice, then one of the two must show a 1, 2, 3, or 4. The probability of this happening is 4/6 = 2/3. However, if one die shows one of these numbers, then the other die must show a 1. The probability for this is 1/6. And this is true for the other 3 possible values of die 1, as shown in this table:
1 4
2 3
3 2
4 1
So, the probability that the first die will show a number between 1 and 4 is 2/3, but the probability that the second die will show the corresponding value is only 1/6. Since the rolling of each die is independent of the other die, the two are independent, so the probability of getting 5 is found my multiplying these two probabilities:
2/3 · 1/6 = 2/18 = 1/9
Example 2: Adam, Barbara, Chris, Devin, and Ellen are members of a class, and 3 of them will be randomly selected as a committee to plan a class party. What is the probability that both Barbara and Devin will be on the committee?
Solution: This is an application of combinations to probability. First, we calculate the number of possible committees of 3 taken from these 5 people. This is the same as
\(\begin{align} 5 \choose 3\end{align}\), which is equal to
\(\begin{align} \frac {5!}{(5-3)!3!} = \frac {5 \times 4}{2} = 10\end{align}\)
That is, there are 10 possible randomly selected committees. Now, how many of these would include Barbara and Devin? It’s easy to see that there are 3 such committees: {B, D, A}, {B, D, C}, {B, D, E}, where we are using the initials of the people to designate them. Figuring the probability p then, we have
\(\begin{align} \frac {3}{10}\end{align}\)
So the probability of these two, Barbara and Devin, being together on the committee is 3/10.
Example 3: Suppose we have a group of 4 people born during the first 10 days in June. What is the probability that two of them have the same birthday?
Solution: A standard approach to this problem is to calculate the probability that no two of the 4 will have the same birthday. That is, if A is the event that two of them have the same birthday, we’ll calculate the probability of the complement of A. Then we’ll subtract our result from 1 to get the probability of A. We will show our final results as percentages.
Identify the persons as E, F, G, and H. We start with E, who has a birthday between June 1 and June 10. What’s the probability that F does not have the same birthday as E? Since E’s birthday occupies 1 of the 10 days, there are 9 days left for F to choose from, so the probability that F has a different birthday is 9/10 = 90%.
Now, given that E and F have different birthdays, what’s the probability that G will have a birthday different from both E and F. It’s easy to see that this probability is 8/10.
Notice that we are using conditional probability here. Given that E and F have different birthdays, what is the probability that G has a different birthday also? We decided that the probability of this is 8/10. So then what is the total probability that that all three, E, F, and G, have different birthdays? Since their birthdays are independent of each other – that is, they’re independent events – then the probability that all their birthdays are different is the product of the two probabilities: 9/10 · 8/10 = 72/100 = 72%.
Now let’s look at H. Given that E, F, and G all have different birthdays, what’s the probability that H will also? Obviously, 3 of the 10 days are already taken, so the probability for H’s birthday to be different must be 7/10. And the total probability for all 4 people to have different birthdays is 9/10 · 8/10 · 7/10 = 504/1000, or in other words, 50.4%.
To get the probability that two of them will have the same birthday we subtract this percentage from 100%, and we get
100% – 50.4% = 49.6%