10.10: Counting Rules (Webb)

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 m₂ 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 m₁·m₂···m_n.

Example 4-25

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.

Example 4-26

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.

Example 4-27

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 [2^nd] [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).

Example 4-28

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: _nP_r), 3 for combination (3: _nC_r). Enter the number of “successes” (r). Press [ENTER] to calculate.

TI-89: Press [2nd] Math > 7:Probability > Press 2 for permutation (2: _nP_r), 3 for combination (3: _nC_r). 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

Example 4-30

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, 1^st, 2^nd, or 3^rd place or prize, etc. then the order in which the items are arranged is important and you would use permutation.

Example 4-31

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.

Example 4-32

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.

https://www.oregonlottery.org/jackpot/pick-4/

Solution

There is only one winning number, so the numerator for the probability will just be 1. The denominator will be all the ways to select the 4 numbers. Repeat numbers are allowed, for example you can have 4242 with repeating 4s and 2s. The order in which the balls are selected does matter by the rules of the game. Use the fundamental counting rule combined with the fundamental counting rule and we would get 10·10·10·10 = 10,000.

Thus, the probability of winning the jackpot would be \(\frac{1}{10000}=0.0001\)

Example 4-33

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 ₁₃C₁ 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 ₄C₃ 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 ₁₂C₁ ways to choose the rank for the pair. Once the pair is chosen there are ₄C₂ ways to choose a pair from that rank. All together there are ₅₂C₅ 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

Example 4-34

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.

https://www.oregonlottery.org/jackpot/powerball/

Solution

There is only one winning number, so the numerator for the probability will just be 1. The denominator will be all the ways to select the 5 white balls and 1 red ball. The order in which the balls are selected does not matter and repeat numbers are not allowed. Using the combination rule combined with the fundamental counting rule we would get ₆₉C₅ ∙ ₂₆C₁.

Thus, the probability of winning the jackpot would be \(\frac{1}{_{69} C_{5} \cdot{}_{26} C_{1}}\) = 0.000000003707.

Example 4-35

An iPhone has a 6 digit numerical password to unlock the phone. What is the probability of guessing the password on the first try?

Solution

There is only one correct password, so the numerator for the probability will just be 1. The denominator will be all the ways to select the 6 numbers. Repeat numbers are allowed. The order in which the numbers are entered into the phone matters. Using the fundamental counting rule, we would get 10 ∙ 10 ∙ 10 ∙ 10 ∙ 10 ∙ 10 = 10⁶ = 1,000,000 possible passwords.

Thus, the probability of guessing the password on the first try would be \(\frac{1}{1000000}=1 \mathrm{E}-6=0.000001\)

“The chances of this happening are more or less one to infinity against. Little is known of how this came about because none of the geophysicists, probability statisticians, meteoranalysts or bizzarrologists who are so keen to research it can afford to stay there.”

(Adams, 2002)