3.8 Counting Rules: Basic Counting Rule, Combination, and Permutation
In order to apply the equal-likely outcome model (the f/N rule) to calculate the probability of a certain event, we need to determine N (the number of all possible outcomes) and f (the number of ways we observe the event). However, if f and N are very large numbers, it can be difficult, or even impossible, to list all possible outcomes that they contain. Fortunately, we can use counting rules to determine the number of ways that something can happen without directly listing all possibilities.
3.8.1 The Basic Counting Rule
Suppose that a job consists of [latex]k[/latex] separate tasks and the [latex]i[/latex]th task can be done in [latex]n_i[/latex] ways, [latex]i= 1, 2, \dots , k[/latex], the basic counting rule states that the entire job can be done in [latex]n_1 \times n_2 \times ... \times n_k[/latex] different ways.
Example: Basic Counting Rule
- An experiment involves tossing a pair of dice and observing the number on the upper faces. Find the number of possible outcomes of this experiment.
The experiment consists of two tasks: observing the outcome of the first die and observing the second die. The number of possible outcomes of the first task is 6 and the number of possible outcomes of the second task is also 6; as a result, the total number of possible outcomes is [latex]6 \times 6 = 36[/latex].
- A restaurant offers a four-course meal consisting of soup, salad, a main course and a dessert. The menu provides three options for soup, two options for salad, four options for the main course, and three options for dessert. Find the total number of different orders for this four-course meal.
By the basic counting rule, number of orders is [latex]3 \times 2 \times 4 \times 3=72[/latex].
- Determine the number of ways to arrange three objects in order.
Arranging three objects in order consists of three tasks:
1) choose the object to be placed in the first spot,
2) choose the object to be placed in the second spot, and
3) choose the object to be placed in the third spot.
There are three objects; therefore, there are three options for the first spot, two for the second spot and only one for the last spot. By the basic counting rule, there are [latex]3 \times 2 \times 1=3!=6[/latex] ways to arrange three objects in order. More generally, there are [latex]n \times (n-1) \times \cdots \times 1 = n![/latex] ways to arrange n objects in order. The notation [latex]n![/latex] is read as n factorial. Note that [latex]0!=1[/latex].
3.8.2 Combination: Order Does Not Matter
A combination of [latex]r[/latex] objects from a collection of [latex]n[/latex] objects is any unordered arrangement of [latex]r[/latex] of the [latex]n[/latex] objects—in other words, any subset of [latex]r[/latex] objects from the collection of [latex]n[/latex] objects. The number of possible combinations of [latex]r[/latex] objects that can be formed from [latex]n[/latex] objects is denoted as [latex]_nC_r[/latex] (read as “n choose r”) and can be calculated as [latex]_nC_r = \frac {n!}{r!(n-r)!}.[/latex]
For example, if a hand of 5 cards is dealt from a deck of 52 cards, the order does not matter. There are [latex]_{52}C_5=\frac{52!}{5!(52-5)!}=\frac{52!}{5!47!}=2,598,960[/latex] different hands.
Here is an intuitive argument for the formula. The [latex]n[/latex] objects are divided into two parts: those [latex]r[/latex] objects that are chosen and those [latex](n-r)[/latex] objects that are unselected. The number of unordered arrangements of [latex]r[/latex] objects taken from [latex]n[/latex] objects equals to the number of ordered arrangements of [latex]n[/latex] objects divided by the number of ways that we could arrange the [latex]r[/latex] selected objects and those [latex](n-r)[/latex] unselected objects in order. There are [latex]n![/latex] ways to arrange [latex]n[/latex] objects in order, [latex]r![/latex] ways to arrange those r selected objects and [latex](n-r)![/latex] ways to arrange those [latex](n-r)[/latex] unselected objects in order. By the basic counting rule, the number of ways to arrange those [latex]r[/latex] selected and [latex](n-r)[/latex] unselected objects is [latex]r!(n-r)![/latex]. Therefore, the number of unordered arrangements of [latex]r[/latex] objects taken from [latex]n[/latex] objects is given by [latex]_nC_r = \frac {n!}{r!(n-r)!}.[/latex]
3.8.3 Permutation: Order Does Matter
A permutation of [latex]r[/latex] objects from a collection of [latex]n[/latex] objects is any ordered arrangement of [latex]r[/latex] of the [latex]n[/latex] objects. The number of possible permutations of [latex]r[/latex] objects that can be formed from [latex]n[/latex] objects is denoted as [latex]_nP_r[/latex] (read as “n permute r”) and can be calculated as [latex]_nP_r = \frac{n!}{(n-r)!}.[/latex]
For example, if a passcode consists of four different digits from 0 to 9, order of the four digits matters. There are [latex]_{10}P_4 = \frac{10!}{(10-4)!}=10\times 9\times 8\times 7=5040[/latex] distinguish passcodes.
We can consider the permutation as a two-step procedure: we first choose [latex]r[/latex] objects of [latex]n[/latex] objects and then arrange them in order. There are [latex]_nC_r[/latex] ways to choose [latex]r[/latex] objects of [latex]n[/latex] objects and there are [latex]r![/latex] different ways to arrange [latex]r[/latex] objects in order. By the basic counting rule, [latex]_nP_r =_nC_r \times r! = \frac{n!}{r!(n-r)!} \times r! = \frac{n!}{(n-r)!}.[/latex]
Alternatively, we can view the permutation as a truncated version of the factorial function. That is, we arrange [latex]r[/latex] of the [latex]n[/latex] objects in order: there are [latex]n[/latex] ways to pick the first object, [latex]n-1[/latex] ways to pick the second object, …, and [latex]n-r+1[/latex] ways to pick the [latex]r[/latex]th object. Hence, by the basic counting rule, [latex]_nP_r = n \times (n-1) \times\cdots\times (n-r +1).[/latex]
Multiplying by [latex]\frac{(n-r)!}{(n-r)!}[/latex] gives [latex]_nP_r = \frac{n!}{(n-r)!}.[/latex]
Exercise: Combinations and Permutations
- Suppose a population consists of [latex]N =3[/latex] students (A, B, and C). If we take a simple random sample of size [latex]n=2[/latex], find the number of different samples.
- Suppose three students run for two positions: president and vice-president. Find the number of possible outcomes.
- Lotto 649 is a lottery that costs $3 to play and requires you to pick 6 numbers between 1 and 49, without replacement. You win the jackpot if your six numbers match the six winning numbers, and order does not matter. According to national-lottery.com, the average Jackpot between January 1, 2020 and May 20, 2020 was about $9,000,000. Find the probability of winning a jackpot. Do you think it is wise to play Lotto 649?
Show/Hide Answer
- Steps:
- Does order matter? (No, just want two students, no ordered arrangement is needed)
- Use combination:
| Sample (n=2) |
| A, B |
| A, C |
| B, C |
- Steps:
- Does order matter? (Yes, need to choose two students and then assign them to president or vice president.)
- Use permutation: [latex]_3P_2 = _3C_2 \times 2! = 3 \times 2 = 6.[/latex]
| President | Vice President |
| A | B |
| B | A |
| A | C |
| C | A |
| B | C |
| C | B |
- Steps:
- Does order matter? (No, only need to choose six numbers between 1 and 49, order does not matter)
- Use permutation: [latex]_{49}C_6 = 13,983,816.[/latex]
Choose six numbers out of 49, there are [latex]_{49}C_6 = 13,983,816[/latex] combinations, but only one combination will match those six winning numbers. Therefore, the probability of winning jackpot is
[latex]P(Jackpot) = \frac{f}{N} = \frac{1}{_{49}C_6} = \frac{1}{13,983,816} = 0.0000000715.[/latex]
One Lotto 649 ticket costs $3. If you try all [latex]_{49}C_6 = 13,983,816[/latex] possible combinations at a cost of
[latex]13,983,816 \times 3 = \$41,951,448.[/latex]
That is, in order to guarantee winning the Jackpot, you need to spend more than $30,000,000 more than the average winnings in the first 4 months of 2020. This is clearly not a good way to spend your money!
Exercise: Probability Rules and Counting Rules
1. Roll three balanced dice,
a) find the probability of rolling all 6s.
b) find the probability that all the dice come up the same number.
2. Suppose that STAT 151 has four sections, and that three students each randomly pick a section. Find the probability that
a) all three students end up in the same section.
b) all three students end up in different sections.
c) nobody picks the first section.
3. Five men and three women sit together in a row. Find the probability that
a) the same gender is at each end.
b) the three women all sit together.
Show/Hide Answer
1.
- The three dice are independent and each has a 1/6 probability of rolling a six. By the special multiplication rule [latex]P(E) = \frac{1}{6} \times \frac{1}{6} \times \frac{1}{6}[/latex].
- Using the same reasoning as in part (a), we conclude that each of the six faces has a [latex](\frac{1}{6})^3[/latex] probability of occurring 3 consecutive times. Since there are 6 possible outcomes, it follows that [latex]P(E) =6 \times \frac{1}{6} \times \frac{1}{6} \times \frac{1}{6}[/latex].
2.
- [latex]\frac{f}{N} = \frac{4 \times 1 \times 1}{4 \times 4 \times 4}[/latex]. Each student has four choices, so [latex]N = 4 \times 4 \times 4[/latex]. In order for all three students to end up in the same section, the first student has four choices, while the second and third students have to pick the same section as the first student. Hence, [latex]f = 4 \times 1 \times 1[/latex].
- [latex]\frac{f}{N} = \frac{4 \times 3 \times 2}{4 \times 4 \times 4}[/latex]. In order for all three students to end up in different sections, the first student has four choices, the second student has three choices and third student has two choices. Hence, [latex]f = 4 \times 3 \times 2[/latex].
- [latex]\frac{f}{N} = \frac{3 \times 3 \times 3}{4 \times 4 \times 4}[/latex]. Since the only condition is that no student can choose the first section, it follows that everyone has three choices, and so [latex]f = 3 \times 3 \times 3[/latex].
3.
- [latex]\frac{f}{N} = \frac{\binom{5}{2}2!6! + \binom{3}{2} 2! 6!}{8!}[/latex]. Note that the notation [latex]\binom{3}{2}[/latex] is the same as [latex]_3C_2[/latex]. Eight people can be ordered in [latex]N = 8![/latex] ways. In order to count the number of ways for the individuals at either end to be of the same gender, we consider two cases.
-
- Case 1: men on each end. First, there are [latex]\binom{5}{2}[/latex] (five choose 2) ways choose two of the five men to sit at either end. Next, there are 2! ways to arrange these two men in order. Finally, the remaining six people (three men and three women) can be arranged in 6! ways. By the basic counting rule, there are [latex]\binom{5}{2}2!6![/latex] different arrangements with a man on each end.
- Case 2: women on each end. First, there are [latex]\binom{3}{2}[/latex] (three choose 2) ways to choose two of the three women to sit at either end. Next, there are 2! ways to arrange these two women in order. Finally, the remaining six people (five men and one woman) can be arranged in 6! ways. By the basic counting rule, there are [latex]\binom{3}{2}2!6![/latex] different arrangements with a woman on each end.
Combining cases 1 and 2, we see that there is a total of [latex]\binom{5}{2}2!6! +\binom{3}{2}2!6![/latex] different arrangements with individuals of the same gender seated on each end.
b. [latex]\frac{f}{N} = \frac{3!6!}{8!}[/latex]. Once again, eight people can be ordered in [latex]N=8![/latex] ways. To determine the number of reorderings with all three women together, it is easiest to view the three women as one item in an ordered arrangement with five men: ({W,W,W},M,M,M,M,M). Notice that six items can be reordered in 6! ways, and that the 3 women within the first item can be reordered in 3! ways. Therefore [latex]f= 3!6![/latex].
