3.7: Counting Rules
- Page ID
- 36659
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)- Use the Fundamental Counting Rule
- Compute factorials, permutations and combinations
- Understand when to use each method
- Find probabilities using counting rules
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
Fundamental Counting Rule: If event 1 can be done m1 ways, event 2 can be done m2 ways, and so forth to event n being done mn ways, then the number of ways to do event 1, followed by event 2,…, followed by event n together would be to multiply the number of ways for each event: 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 events: choosing a salad, a main dish, and a dessert. There are 3 choices for salad, 8 choices for the main dish, and 5 choices for dessert. The ways to choose a salad, main dish, and dessert are: \(\underset{\overline{\text { salad }}} {3} \times \underset{\overline{\text { main dish }}}{8} \times \underset{\overline{\text{ dessert }}}{5}\) = 120 different meals.
How many 4-digit debit card personal identification numbers (PIN) can be made?
Solution
There are four events in this example. The events are picking the first number, then the second number, then the third number, and then the fourth number. The first event can be done 10 ways since the choices are the numbers 1 through 9 and 0. We can use the same numbers over again (repeats are allowed) for the second number, so it can also be done 10 ways. The same with the third and fourth numbers, which also have 10 choices.
There are \(\underset{\overline{\text { first number }}}{10} \times \underset{\overline{\text { second number }}}{10} \times \underset{\overline{\text { third number }}}{10} \times \underset{\overline{\text { fourth number }}}{10} \) = 10,000 possible PINs.
How many ways can the three letters a, b, and c be arranged with no letters repeating?
Solution
There are three events in this case. The events are to pick the first letter, then the second letter, and then the third letter. The first event can be done 3 ways since there are 3 letters. The second event can be done 2 ways, since the first event took one of the letters (repeats are not allowed). The third event can be done 1 way, since the first and second events took 2 of the letters.
There are \(\underset{\overline{\text { first letter }}}{3} \times \underset{\overline{\text { second letter }}}{2} \times \underset{\overline{\text { third letter }}}{1} \) = 6 ways to arrange the letters.
You can also use the tree diagram in Figure \(\PageIndex{1}\) to visualize the arrangements. There are 6 different arrangements of the letters, which can be found by multiplying 3·2·1 = 6.
Figure \(\PageIndex{1}\)
Factorials, Permutations and Combinations
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 for the factorial.
Factorial Rule: The number of different ways to arrange n distinct objects is
\(n! = n \cdot (n – 1) \cdot (n – 2) \ldots \cdot 3 \cdot 2\cdot 1\), where repetitions are not allowed.
0 factorial is defined to be 0! = 1 and 1 factorial is defined to be 1! = 1.
TI-84 Plus: Enter the number of which you would like to find the factorial. Press [MATH]. Use cursor keys to move to the PRB (or PROB) menu. Press 4 (4:!). Press [ENTER] to calculate.
Excel: In an empty cell type in =FACT(n), where n is the number of which you would like to find the factorial. Thus 4! would be =FACT(4).
How many ways can you arrange 5 people standing in line?
Solution
No repeats are allowed since you cannot reuse a person twice in the line. Order is important since the first person is first in line and will be selected first. This meets the requirements for the factorial rule. There are 5! = 5·4·3·2·1 = 120 ways to arrange 5 people standing in line.
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 distinct total objects when repeats are not allowed and order matters is \({ }_{n} P_{r} = P(n, r) = \dfrac{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 distinct total objects when repeats are not allowed and order does not matter is \({ }_{n} C_{r} = C(n, r) = \dfrac{n !}{r !(n-r) !}\).
TI-84 Plus: Enter the number of total objects (n). Press [MATH]. Use cursor keys to move to the PRB (or PROB) menu. Press 2 for permutation (2: nPr), or 3 for combination (3: nCr). Enter the number of objects to be selected (r). Press [ENTER] to calculate.
Excel: In a blank cell, type the formula =COMBIN(n, r) or =PERMUT(n, r) where n is the total number of objects and r is the number of objects that you are selecting. For example, =COMBIN(8, 3).
The following flow chart in Figure \(\PageIndex{2}\) may help with deciding which counting rule to use.
Start at the top: 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 use a combination. If it does, then ask if you are ordering the entire group. If so, use a factorial. If only ordering some from the total, use a permutation.
Figure \(\PageIndex{2}\)
Circle K International, a college community service club, has 15 members this year. How many ways can a board of officers consisting of a president, vice-president, secretary and treasurer be elected?
Solution
In this case, repeats are not allowed since the same member cannot hold more than one position. The order matters because if you elect person 1 for president and person 2 for vice-president, there would be different members in those positions than if you elect person 2 for president, person 1 for vice-president. Thus, this is a permutation problem with n = 15 and r = 4. There are \({ }_{15} P_{4}=\dfrac{15 !}{(15-4) !}=\dfrac{15 !}{11 !}=32,760 \) ways to elect the 4 officers.
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.
Circle K International, a college community service club, has 15 members this year. They need to select 2 members to be representatives for the school's Inter-Club Council. How many ways can the 2 members be chosen?
Solution
In this case, repeats are not allowed, since there must be 2 different members as representatives. The order in which the representatives are selected does not matter since they have the same position. Thus, this is a combination problem with n = 15 and r = 2. There are \({ }_{15} C_{2} =\dfrac{15 !}{2 !(15-2) !}=\dfrac{15 !}{2 ! \cdot 13 !} = 105\) ways to select 2 representatives.
The counting rules can be used in the probability rules to calculate the number of ways that an event can occur.
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
In this case, repeats are allowed for the password. The order in which the numbers are entered into the phone matters. Thus, the Fundamental Counting Rule must be used to find the total number of possible passwords. There are 1010
10
10
10
10 = 106 = 1,000,000 possible passwords. There is only one correct password, so the number of ways to correctly guess is 1. Thus, the probability of guessing the password correctly on the first try is \(P(\text{correct guess}) = \dfrac{\text{Number of ways to guess correctly}}{\text{Number of possible passwords}} = \dfrac{1}{1,000,000} = 1 \times 10^{-6} = 0.000001\).
What is the probability of winning the jackpot in the Powerball Lottery? To play, you must pick 5 numbers between 1 and 69, and pick one Power Number between 1 and 26. You must match all 6 numbers to win the jackpot. (https://www.calottery.com/draw-games/powerball)
Solution
In this case, repeats are not allowed for the 5 numbers since there must be 5 different numbers selected. The Power Number is selected separately, and may be the same as one of the first 5 numbers selected. Since the order that the 5 numbers are selected does not matter, the total number of different ways to pick 5 is a combination. There are \({}_{69} C_{5} = \dfrac{69!}{5!(69-5)!} = \dfrac{69!}{5! \cdot 64!}\) = 11,238,513 ways to pick 5 numbers from 1 to 69. There are \({}_{26} C_{1}\) = 26 ways to pick a Power Number. By the Fundamental Counting Rule, there are 11,238,513 26 = 292,201,338 ways to pick 5 numbers plus a Power Number. There is only one winning combination, so the number of ways to win is 1. Thus, the probability of winning is \(P(\text{win}) = \dfrac{\text{Number of ways to win}}{\text{Number of different ways to play}} = \dfrac{1}{292,201,338} = 3.42 \times 10^{-9} \approx 0.00000000342\). This is an astronomically small chance of winning the jackpot!
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 consists of 3-of-a-kind and a pair. For example, 3 queens and a pair of 2s. There are \({}_{13} C_{1}\) ways to choose a card between ace, 2, 3, … king for the 3-of-a-kind. Once a card is chosen, there are 4 cards with that rank and there are \({}_{4} C_{3}\) ways to choose a 3-of-a-kind from that rank. Since the card chosen for the 3-of-a-kind cannot be chosen for the pair, there are \({}_{12} C_{1}\) ways to choose a card for the pair. Once a card is chosen for the pair, there are \({}_{4} C_{2}\) ways to choose a pair from that rank. All together there are \({}_{52} C_{5}\) ways to randomly deal 5 cards from a deck. Using the Fundamental Counting Rule, the probability of getting a full house is \(P(\text{full house}) = \dfrac{ {}_{13} C_{1} \times {}_{4} C_{3} \times {}_{12} C_{1} \times {}_{4} C_{2} }{ {}_{52} C_{5} } = \dfrac{13 \times 4 \times 12 \times 6}{2,598,960} = \dfrac{3744}{2,598,960} = 0.00144\).