4.6: Counting Rules
- Page ID
- 45476
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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}\)
- Apply counting rules to determine the number of possible ways events can occur.
- Use the fundamental counting rule by multiplying the number of choices for each step in a sequence.
- Calculate permutations to count arrangements where order matters.
- Calculate combinations to count selections where order does not matter.
Sometimes the sample space or event space is extremely large, and it isn’t feasible to write it out. In that case, mathematical tools can be used for counting the size of the sample space and event space. These tools are known as counting techniques.
Multiplication Rule
Is used to compute the total number of possibilities for a sequence of events.
If event#1 can be done \(m_{1}\) ways, event#2 can be done \(m_{2}\) ways, and so forth to event#n being done \(m_{n}\) ways. Then the number of ways to do all the events together would be \(m_{1}\) \(\cdot\) \(m_{2}\) \(\cdot\)\(\cdot\)\(\cdot\) \(m_{n}\).
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
\(3 \cdot 8 \cdot 5 = 120\)
There are 120 different meals that are possible.
How many three-letter “words” can be made from the letters a, b, and c with no letters repeating? A “word” is just an ordered group of letters. It doesn’t have to be a real word in a dictionary.
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. The third task can be done 1 way since the first and second tasks took two of the letters. There are
\(3 \cdot 2 \cdot 1=6\)
So, there are 6 different possibilities.
In Example \(\PageIndex{2}\), the solution was found by find \(3*2*1=6\). Many counting problems involve multiplying a list of decreasing numbers. This is called a factorial. There is a special symbol for this and a special button on your calculator.
Factorial
\(n !=n(n-1)(n-2) \cdots(3)(2)(1)\)
As an example:
\(5 !=5\) \(\cdot\) \(4\) \(\cdot\) \(3\) \(\cdot\) \(2\) \(\cdot\) \(1=120\)
\(8 !=8\) \(\cdot\) \(7\) \(\cdot\) \(6\) \(\cdot\) \(5\) \(\cdot\) \(4\) \(\cdot\) \(3\) \(\cdot\) \(2\) \(\cdot\) \(1=40320\)
0 factorial is defined to be 0!=1 and 1 factorial is defined to be 1!=1.
To use a TI-84 + calculator to compute a factorial perform the following steps for the example.
5!
- Press the [MATH] button.
- Use the right arrow key to scroll to the [PRB] menu.
- Select option [4: !] by either scrolling down and pressing ENTER or simply pressing 4.
- You should now see 5! on the screen.
- Press ENTER to compute the factorial.
The answer for 5! should be 120.
Permutation Rule for "n" Distinct Objects
The total number of permutations for n distinct objects that do not repeat is n!
- How many different batting orders are possible for a group of 9 batters?
- A group of 6 students enter a line to purchase coffee at a local coffee shop. How many different lines are possible?
- An athlete has 4 trophies on her shelf. How many ways can she arrange the trophies to display them?
Solutions
- \(9 !=9\) \(\cdot\) \(8\) \(\cdot\) \(7\) \(\cdot\) \(6\) \(\cdot\) \(5\) \(\cdot\) \(4\) \(\cdot\) \(3\) \(\cdot\) \(2\) \(\cdot\) \(1=362,880\)
- \(6 !=6\) \(\cdot\) \(5\) \(\cdot\) \(4\) \(\cdot\) \(3\) \(\cdot\) \(2\) \(\cdot\) \(1=720\)
- \(4!=4\) \(\cdot\) \(3\) \(\cdot\) \(2\) \(\cdot\) \(1=24\)
If objects in the group are not distinct and repeat, a different formula must be used to compute the total number of permutations. This formula will divide out all the repetitions.
The total number of permutations of n objects in which object 1 repeats \(r_{1}\) times, object 2 repeats \(r_{2}\) times, object 3 repeats \(r_{3}\) times, etc. is computed as follows:
\(\dfrac{n!}{r_1!\cdot r_2!\cdot\cdot\cdot r_n!}\)
- For the word "STATISTICS" find the total number of permutations.
- How many different ways can 5 identical dinosaur toys, 3 identical helicopter toys, and 4 identical action figures be arranged in a grocery store counter display?
Solutions
For this problem, there are 10 letters. Thus, n = 10. S repeats two times, T repeats three times, A occurs once, I repeats two times, and C occurs once. When dividing only include the number of repetitions for letters with repetitions greater than one.
- \(\dfrac{10!}{2!\cdot 3!\cdot 2!}\)\(=\)\(\dfrac{10!}{2\cdot 6\cdot 2}\)\(=\)\(\dfrac{3,628,800}{24}\)\(=151,200\)
- \(\dfrac{12!}{5!\cdot 3!\cdot 4!}\)\(=\)\(\dfrac{12!}{120\cdot 6\cdot 24}\)\(=\)\(\dfrac{479,001,600}{17,280}\)\(=27,720\)
Sometimes a sample space depends on selecting r objects from n total objects. The number of ways to do this depends on whether the order in which the r objects matters or if it doesn’t. For example, if a person needs to call another on the phone, they must have the correct number in the right order. Otherwise, the wrong number will be called. In this case, the order of the numbers matters. However, if numbers were selected randomly for playing the lottery, it doesn’t matter which number is picked first. As long as the selection matches the numbers chosen by the lottery, the jackpot will be won. In this case, the order doesn’t matter. A permutation is an arrangement of items in a specific order. Permutations are used to count items when the ordering of the items matters. When the order of the items doesn’t matter, combinations are used. A combination is an arrangement of items when order is not important. When computing a counting problem, the first question should be “does order matter?”
Permutation Formula
Picking r objects from n total objects when order matters
\(_{n} P_{r}=\dfrac{n !}{(n-r) !}\)
In a club with 15 members, how many ways can a slate of 3 officers consisting of a president, vice-president, and secretary/treasurer be chosen?
Solution
In this case the order matters. If you pick person 1 for president, person 2 for vice-president, and person 3 for secretary/treasurer you would have different officers than if you picked person 2 for president, person 1 for vice-president, and person 3 for secretary/treasurer. This is a permutation problem with n=15 and r=3.
\(_{15} P_{3}=\dfrac{15 !}{(15-3) !}=\dfrac{15 !}{12 !}=2,730\)
To use a TI-84 + calculator to compute a permutation for 15 choose 3 and perform the following steps.
\(_{15} P_{3}\)
- Enter 15 (since we are choosing from 15 items).
- Press the [MATH] button.
- Use the right arrow key to navigate to the [PRB] menu.
- Select [2: nPr] by either scrolling down and pressing [ENTER] or simply pressing 2.
- Enter 3 (since we are selecting 3 items).
- Press [ENTER] to compute the result.
The answer is 2,730.
A school club has 25 members, and we need to select a President, Vice President, Treasurer, and Secretary from the group. How many ways can this be done?
Solution
Since the positions are different, the order in which they are selected is important. In this \(n = 25\) and \(r = 4\).
\(_{25} P_{4}=\dfrac{25 !}{(25-4) !}=\dfrac{25 !}{21 !}=303,600\)
In how many different ways can an ID card number be created using a 6-digit sequence?
Solution
Since order matters, each unique sequence of ID numbers represents a distinct identification number. Additionally, since there are 10 possible digits to choose from (0–9), we have \(n=10\), and since 6 digits are selected, we set \(r=6\).
\(_{10} P_{6}=\dfrac{10!}{(10-6) !}=\dfrac{10!}{4!}=151,200\)
Combination Formula
Picking r objects from n total objects when order doesn’t matter
\(_{n} C_{r}=\dfrac{n !}{r !(n-r) !}\)
Suppose a college basketball team needs to select 7 players from a roster of 20 players to participate in a special training camp. How many ways can you do this?
Solution
In this scenario, the order of selection does not matter, as you are simply choosing 7 players from the group. Therefore, this is a combination problem, where \(n = 20\) (total players) and \(r = 7\) (players selected).
\(_{20} C_{7}=\dfrac{20 !}{7 !(20-7) !}=\dfrac{20 !}{7 ! 13 !}=77,520\)
To use a TI-84 + calculator to compute a combination for 20 choose 7 and perform the following steps.
\(_{20} C_{7}\)
- Enter 20 (since we are choosing from 20 items).
- Press the [MATH] button.
- Use the right arrow key to navigate to the [PRB] menu.
- Select [3: nCr] by either scrolling down and pressing [ENTER] or simply pressing 3.
- Enter 7 (since we are selecting 7 items).
- Press [ENTER] to compute the result.
The answer is 77,520.
How many ways can 5 cards be selected from a deck of 52 cards?
Solution
In this scenario, the order of selection does not matter, as you are simply choosing 5 cards from the group of 52 cards. Therefore, this is a combination problem, where \(n = 52\) (total cards) and \(r = 5\) (cards selected).
\(_{52} C_{5}=\dfrac{52!}{5 !(52-5) !}=\dfrac{52 !}{5 ! 47 !}=2,598,960\)
Most calculators have a factorial button and many have combination and permutation functions.
Authors
"4.6: Counting Rules" by Toros Berberyan, Tracy Nguyen, and Alfie Swan is licensed under CC BY-SA 4.0
Attributions
"4.4: Counting Techniques" by Kathryn Kozak is licensed under CC BY-SA 4.0