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{\longvect}{\overrightarrow}\)
\( \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 #1: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 enters 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.
Permutation Rule #1: Permutation Rule for "n" Distinct Objects in Which Objects Repeat
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 Rule #3: Permutation Formula for Permutations of "r" Objects Chosen from "n" Objects
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.
Exercises
A sociology department is forming a research panel consisting of 1 sociologist, 1 psychologist, and 1 economist. There are 5 sociologists, 4 psychologists, and 6 economists available. How many different panels can be formed?
- Answer
-
Use the counting rule to answer the question.
\(5 \cdot 4 \cdot 6 = 120\)
A community study surveys individuals based on three characteristics: education level (high school, associate degree, bachelor’s degree, graduate degree), employment status (employed, unemployed), and housing status (rent, own). How many different possible combinations of responses are there?
- Answer
-
Use the counting rule to answer the question.
\(4 \cdot 2 \cdot 2= 16\)
A political science researcher is designing a focus group by selecting 1 participant from each of the following groups: 10 urban residents, 12 suburban residents, and 8 rural residents. How many different focus groups can be created?
- Answer
-
Use the counting rule to answer the question.
\(10 \cdot 12 \cdot 8= 960\)
Compute the following factorials.
- 10!
- \(\dfrac{8!}{4!}\)
- Answer
-
- 10! = 3,628,800
- \(\dfrac{8!}{4!} = \dfrac{40,320}{24} = 1,680\)
A college baseball coach must decide the batting order for 9 players in the starting lineup. Since the order of the players matters, in how many different ways can the 9 players be arranged in the batting lineup?
- Answer
-
Use permutation rule #1.
9! = 362,880
A speech class is selecting 6 students to present their speeches, and the order of presentations matters. In how many different ways can the 6 students be arranged for presentation?
- Answer
-
Use permutation rule #1.
6! = 720
A student has 7 different books and wants to arrange them on a bookshelf. Since the order of the books matters, in how many different ways can the 7 books be arranged?
- Answer
-
Use permutation rule #1.
7! = 5,040
A linguistics student is analyzing the word “SUCCESS” for a class project. How many different, distinct arrangements of the letters in the word can be formed?
- Answer
-
Use permutation rule #2.
\(\dfrac{7!}{3! \cdot 2! \cdot 1! \cdot 1!} = \dfrac{5040}{12} = 420\)
A computer science student is creating a code using the symbols ####, &&&, and ** (that is, 4 hashtags, 3 ampersands, and 2 asterisks). If all symbols are arranged in a sequence, how many different unique code words can be formed?
- Answer
-
Use permutation rule #2.
\(\dfrac{9!}{4! \cdot 3! \cdot 2!} = \dfrac{3,628,880}{288} = 1,260\)
An art history class has 40 famous paintings to feature in a gallery spotlight. The curator will choose 4 paintings and decide the order in which they are displayed (first and second). How many different orders of 4 paintings can be selected?
- Answer
-
Use permutation rule #3.
\(_{40}P_{4} = 2,193,360\)
A literature club is selecting 3 different novels from a list of 10 to discuss over two weeks, where the order of discussion matters (which book is read first and which is read second). How many possible ordered selections are there?
- Answer
-
Use permutation rule #3.
\(_{10}P_{3} = 720\)
A communications department is selecting 4 students from 28 to deliver opening and closing speeches at an event. Since the roles are different, order matters, how many different ways can the students be assigned to these four roles?
- Answer
-
Use permutation rule #3.
\(_{28}P_{4} = 491,400\)
A music appreciation class has 8 songs, and the instructor will select 3 of them to analyze in class. Since the order does not matter, how many different groups of 3 can be selected?
- Answer
-
Use the combination rule.
\(_{8}C_{3} = 56\)
A film studies club is choosing 5 movies from a list of 30 to screen during the semester. The order in which they are shown is not important. How many different combinations of 5 movies can be selected?
- Answer
-
Use the combination rule.
\(_{30}C_{5} = 142,506\)
A psychology study is forming a pair of participants by selecting 3 people out of 16 volunteers. Since both participants have equal roles, how many different groups of 3 can be formed?
- Answer
-
Use the combination rule.
\(_{16}C_{3} = 560\)
An economics conference is selecting a panel of 4 speakers from two groups: 6 graduate students and 5 faculty members. The panel must include exactly 2 graduate students and 2 faculty members. How many different panels can be formed?
- Answer
-
Use the combination rule.
\(_{6}C_{2} \cdot _{5}C_{2}= 15 \cdot 10 = 150\)
A cultural studies class is forming a project team of 6 students from a group that includes 10 history majors, 6 psychology majors, and 9 communication majors. The team must include exactly 2 students from each major. How many different teams can be formed?
- Answer
-
Use the combination rule.
\(_{10}C_{2} \cdot _{6}C_{2} \cdot _{9}C_{2}= 45 \cdot 15 \cdot 36= 24,300\)
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