4.7: Counting Rules
- Page ID
- 26148
There are times when the sample space is very large and is not feasible to write out. In that case, it helps to have mathematical tools for counting the size of the sample space. These tools are known as counting techniques or counting rules.
Fundamental Counting Rule: If task 1 can be done m1 ways, task 2 can be done m2 ways, and so forth to task n being done mn ways. Then the number of ways to do task 1, 2,…, n together would be to multiply the number of ways for each task m1·m2···mn.
A menu offers a choice of 3 salads, 8 main dishes, and 5 desserts. How many different meals consisting of one salad, one main dish, and one dessert are possible?
Solution
There are three tasks, picking a salad, a main dish, and a dessert. The salad task can be done 3 ways, the main dish task can be done 8 ways, and the dessert task can be done 5 ways. The ways to pick a salad, main dish, and dessert are: \(\frac{3}{\text { salad }} \cdot \frac{2}{\text { main }} \cdot \frac{1}{\text { dessert }}\) = 120 different meals.
How many 4-digit debit card personal identification numbers (PIN) can be made?
Solution
Four tasks must be done in this example. The tasks are to pick the first number, then the second number, then the third number, and then the fourth number. The first task can be done 10 ways since there are digits 1 through 9 or a zero. We can use the same numbers over again (repeats are allowed) to find that the second task can also be done 10 ways. The same with the third and fourth tasks, which also have 10 ways.
There are \(\frac{10}{\text { first number }} \cdot \frac{10}{\text { second number }} \cdot \frac{10}{\text { third number }} \cdot \frac{10}{\text { fourth number }}\) = 10,000 possible PINs.
How many ways can the three letters a, b, and c be arranged with no letters repeating?
Solution
Three tasks must be done in this case. The tasks are to pick the first letter, then the second letter, and then the third letter. The first task can be done 3 ways since there are 3 letters. The second task can be done 2 ways, since the first task took one of the letters (repeats are not allowed). The third task can be done 1 way, since the first and second task took two of the letters.
There are \(\frac{3}{1^{\text {st }} \text { letter }} \cdot \frac{2}{2^{\text {nd }} \text { letter }} \cdot \frac{1}{3^{\text {rd }} \text { letter }}\)
You can also look at this example in a tree diagram, see Figure 4-17. There are 6 different arrangements of the letters. The solution was found by multiplying 3·2·1 = 6.
Figure 4-17
If we have 10 different letters for, say, a password, the tree diagram would be very time-consuming to make because of the length of options and tasks, so we have some shortcut formulas that help count these arrangements.
Many counting problems involve multiplying a list of decreasing numbers, which is called a factorial. The factorial is represented mathematically by the starting number followed by an exclamation point, in this case 3! = 3·2·1 = 6. There is a special symbol for this and a special button on your calculator or computer.
Factorial Rule: The number of different ways to arrange n objects is n! = n·(n – 1)·(n – 2) ···3·2·1, where repetitions are not allowed.
Zero factorial is defined to be 0! = 1, and 1 factorial is defined to be 1! = 1.
TI-84: On the home screen, enter the number of which you would like to find the factorial. Press [MATH]. Use cursor keys to move to the PRB menu. Press 4 (4:!) Press [ENTER] to calculate.
TI-89: On the home screen, enter the number of which you would like to find the factorial. Press [2nd] [Math] > 7:Probability > 1:!. Press [ENTER] to calculate.
Excel: In an empty cell type in =FACT(n) where n is the number so 4! would be =FACT(4).
How many ways can you arrange five people standing in line?
Solution
No repeats are allowed since you cannot reuse a person twice. Order is important since the first person is first in line and will be selected first. This meets the requirements for the factorial rule,
5! = 5·4·3·2·1 = 120 ways.
Sometimes we do not want to select the entire group but only select r objects from n total objects. The number of ways to do this depends on if the order you choose the r objects matters or if it does not matter. As an example, if you are trying to call a person on the phone, you have to have the digits of their number in the correct order. In this case, the order of the numbers matters. If you were picking random numbers for the lottery, it does not matter which number you pick first since they always arrange the numbers from the smallest to largest once the numbers are drawn. As long as you have the same numbers that the lottery officials pick, you win. In this case, the order does not matter.
A permutation is an arrangement of items with a specific order. You use permutations to count items when the order matters.
Permutation Rule: The number of different ways of picking r objects from n total objects when repeats are not allowed and order matters \({ }_{\mathrm{n}} \mathrm{P}_{\mathrm{r}}=\frac{n !}{(n-r) !}\).
When the order does not matter, you use combinations. A combination is an arrangement of items when order is not important. When you do a counting problem, the first thing you should ask yourself is “are repeats allowed,” then ask yourself “does order matter?”
Combination Rule: The number of ways to select r objects from n total objects when repeats are not allowed and order does not matter \({ }_{\mathrm{n}} \mathrm{C}_{\mathrm{r}}=\frac{n !}{(r !(n-r) !)}\).
TI-84: Enter the number “trials” (n) on the home screen. Press [MATH]. Use cursor keys to move to the PRB menu. Press 2 for permutation (2: nPr), 3 for combination (3: nCr). Enter the number of “successes” (r). Press [ENTER] to calculate.
TI-89: Press [2nd] Math > 7:Probability > Press 2 for permutation (2: nPr), 3 for combination (3: nCr). Enter the sample size on the home screen, then a comma, then enter the number of “successes,” then end the parenthesis. Press [ENTER] to calculate.
Excel: In a blank cell type in the formula =COMBIN(n, r) or =PERMUT(n, r) where n is the total number of objects and r is the smaller number of objects that you are selecting out of n. For example =COMBIN(8, 3).
The following flow chart in Figure 4-18 may help with deciding which counting rule to use.
Start on the left; ask yourself if the same item can be repeated. For instance, a person on a committee cannot be counted as two distinct people; however, a number on a car license plate may be used twice. If repeats are not allowed, then ask, does the order in which the item is chosen matter? If it does not then we use the combinations, if it does then ask are you ordering the entire group, use factorial, or just some of the group, use permutation.
Figure 4-18
Critical Miss, PSU's Tabletop Gaming Club, has 15 members this term. How many ways can a slate of 3 officers consisting of a president, vice-president, and treasurer be chosen?
Solution
In this case, repeats are not allowed since we don’t want the same member to hold more than one position. The order matters, since if you pick person 1 for president, person 2 for vice-president, and person 3 for treasurer, you would have different members in those positions than if you picked person 2 for president, person 1 for vice-president, and person 3 for treasurer. This is a permutation problem with n = 15 and r = 3.
\(
{ }_{15} \mathrm{P}_{3}=\frac{15 !}{(15-3) !}=\frac{15 !}{12 !}=2730
\)
There are 2,730 ways to elect these three positions.
In general, if you were selecting items that involve rank, a position title, 1st, 2nd, or 3rd place or prize, etc. then the order in which the items are arranged is important and you would use permutation.
Critical Miss, PSU's Tabletop Gaming Club, has 15 members this term. They need to select 3 members to have keys to the game office. How many ways can the 3 members be chosen?
Solution
In this case, repeats are not allowed, because we don’t want one person to have more than one key. The order in which the keys are handed out does not matter. This is a combination problem with n = 15 and r = 3.
\({ }_{15} \mathrm{C}_{3}=\frac{15 !}{(3 !(15-3) !)}=\frac{15 !}{(3 ! \cdot 12 !)}=455 \quad \text { There are } 455 \text { ways to hand out the three keys. }\)
We can use these counting rules in finding probabilities. For instance, the probability of winning the lottery can be found using these counting rules.
What is the probability of winning the jackpot in the Pick-4 Lottery? To play Pick-4, you choose 4 numbers from 0 to 9. This will give you a number between 0000 and 9999. You win the jackpot if you match your 4 numbers in the exact order they are drawn.
What is the probability of getting a full house if 5 cards are randomly dealt from a standard deck of cards?
Solution
A full house is a combined three of a kind and pair, for example, QQQ22. There are 13C1 ways to choose a card between Ace, 2, 3, … , King. Once a number is chosen, there are 4 cards with that rank and there are 4C3 ways to choose a three of kind from that rank. Once we use up one of the ranks, such as the three queens, there are 12C1 ways to choose the rank for the pair. Once the pair is chosen there are 4C2 ways to choose a pair from that rank. All together there are 52C5 ways to randomly deal out 5 cards. The probability of getting a full house with then be
\(\frac{_{13} C_{1} \cdot{ }_{4} C_{3} \cdot{ }_{12} C_{1} \cdot{ }_{4} C_{2}}{_{52} C_{5}}\) = \(\frac{3744}{2598960}\) = 0.00144
What is the probability of winning the Powerball jackpot? As of 2021, the Powerball lottery consists of drawing five white balls in any order numbered 1 through 69, and one red Powerball numbered 1 through 26.