<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />

# Counting Techniques

## Number of ways to choose (and potentially arrange) k objects from a group of n objects.

Estimated13 minsto complete
%
Progress
Practice Counting Techniques

MEMORY METER
This indicates how strong in your memory this concept is
Progress
Estimated13 minsto complete
%
Permutations and Combinations

Suppose you draw two cards from a standard deck (one after the other without replacement).

1. How many outcomes are there?
2. How many ways are there to choose an ace and then a four?
3. What is the probability that you choose an ace and then a four?

### Permutations and Combinations

In order to compute the probability of an event, you need to know the number of outcomes in the sample space and the number of outcomes in the event. Sometimes, determining the number of outcomes takes some work! Here, you will look at three techniques for counting outcomes.

Technique #1: The Fundamental Counting Principle: Use this when there are multiple independent events, each with their own outcomes, and you want to know how many outcomes there are for all the events together.

At the local ice cream shop, there are 5 flavors of homemade ice cream -- vanilla, chocolate, strawberry, cookie dough, and coffee. You can choose to have your ice cream in a dish or in a cone. How many possible ice cream orders are there?

If you list them all out, you will see that there are 10 ice cream orders. For each of the 5 flavors, there are 2 choices for how the ice cream is served (dish or cone). 52=10\begin{align*}5 \cdot 2=10\end{align*}

 Vanilla Dish Chocolate Dish Strawberry Dish Cookie Dough Dish Coffee Dish Vanilla Cone Chocolate Cone Strawberry Cone Cookie Dough Cone Coffee Cone

This idea generalizes to a principle called the Fundamental Counting Principle:

Fundamental Counting Principle: For independent events A\begin{align*}A\end{align*} and B\begin{align*}B\end{align*}, if there are n\begin{align*}n\end{align*} outcomes in event A\begin{align*}A\end{align*} and m\begin{align*}m\end{align*} outcomes in event B\begin{align*}B\end{align*}, then there are nm\begin{align*}n \cdot m\end{align*} outcomes for events A\begin{align*}A\end{align*} and B\begin{align*}B\end{align*} together.

The Fundamental Counting Principle works similarly for more than two events - multiply the number of outcomes in each event together to find the total number of outcomes.

Technique #2: Permutations: Use this when you are counting the number of ways to choose and arrange a given number of objects from a set of objects.

Your sister's 3rd grade class with 28 students recently had a science fair. The teacher chose 1st, 2nd, and 3rd place winners from the class. In how many ways could she have chosen the 1st, 2nd, and 3rd place winners?

This is called a permutation problem because it is asking for the number of ways to choose and arrange 3 students from a set of 28 students.

In this problem, event A\begin{align*}A\end{align*} is the teacher choosing 1st place, event B\begin{align*}B\end{align*} is the teacher choosing 2nd place after 1st place has been chosen, and event C\begin{align*}C\end{align*} is the teacher choosing 3rd place after 1st and 2nd place have been chosen.

• Event A\begin{align*}A\end{align*} has 28 outcomes because there are 28 students in the class. The teacher has 28 choices for 1st place.
• Event B\begin{align*}B\end{align*} has 27 outcomes because once 1st place has been chosen, there are 27 students left in the class that could get 2nd place.
• Event C\begin{align*}C\end{align*} has 26 outcomes because once 1st place and 2nd place have been chosen, there are 26 students left in the class that could get 3rd place.

By the Fundamental Counting Principle, the teacher has 282726=19656\begin{align*}28 \cdot 27 \cdot 26=19656\end{align*} ways in which she could choose the 3 winners. Note that:

\begin{align*}28 \cdot 27 \cdot 26=\frac{28 \cdot 27 \cdot 26 \cdot \bcancel{25 \cdot 24 \cdot 23 \cdots 3 \cdot 2 \cdot 1}}{\bcancel{25 \cdot 24 \cdot 23 \cdots 3 \cdot 2 \cdot 1}}=\frac{28!}{25!}=\frac{28!}{(28-3)!}\end{align*}

This is the idea behind the permutation formula. (Recall that the factorial symbol, !, means to multiply every whole number up to and including that whole number together. For example, \begin{align*}5!=5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\end{align*}.)

Permutation Formula: The number of ways to choose and arrange \begin{align*}k\end{align*} objects from a group of \begin{align*}n\end{align*} objects is:

\begin{align*}_nP_k=\frac{n!}{(n-k)!}\end{align*}

Technique #3: Combinations: Use this when you are counting the number of ways to choose a certain number of objects from a set of objects (the order/arrangement of the objects doesn't matter).

A teacher has a classroom of 28 students, she wants 3 of them to do a presentation, and she wants to know how many choices she has for the three students.

This is called a combination problem because it is asking for the number of ways to choose 3 students from a set of 28 students. With combinations, the order doesn't matter. Choosing Bobby, Sarah, and Matt for the presentation is the same as choosing Sarah, Bobby, and Matt for the presentation.

From permutations, you know that there are 19656 ways to choose and arrange 3 students from the class of 28. This calculation will be counting each group of 3 people more than once. How many times is each group of three being counted? From permutations, 3 chosen people can be arranged in \begin{align*}_3P_3\end{align*} ways.

\begin{align*}_3P_3=\frac{3!}{(3-3)!}=\frac{3!}{0!}=\frac{3!}{1}=3 \cdot 2 \cdot 1=6 \ ways.\end{align*}

This means that every group of three has been counted 6 times in the 19656 calculation. To determine the number of ways the teacher could choose 3 students where the order doesn't matter, take 19656 and divide by 6.

\begin{align*}\frac{19656}{6}=3276\end{align*}

The teacher has 3276 choices for the three students to make a presentation.

In general, the permutation formula can be turned into the combination formula by dividing by the number of ways to arrange \begin{align*}k\end{align*} objects, which is \begin{align*}k!\end{align*}.

Combination Formula: The number of ways to choose \begin{align*}k\end{align*} objects from a group of \begin{align*}n\end{align*} objects is:

\begin{align*}_nC_k=\frac{_nP_k}{k!}=\frac{n!}{k!(n-k)!}\end{align*}

In the problems below you will see how to use the fundamental counting principle, permutations, and combinations to help you compute probabilities. Note that whenever you can use permutations you can also use the fundamental counting principle, because the permutation formula is derived from the fundamental counting principle.

#### Using the Fundamental Counting Principle

Suppose you are ordering a sandwich at the deli. There are 5 choices for bread, 4 choices for meat, 12 choices for vegetables, and 3 choices for a sauce. How many different sandwiches can be ordered? If you choose a sandwich at random, what's the probability that you get turkey and mayonnaise on your sandwich?

In order to answer this probability question you need to know:

1. The total number of sandwiches that can be ordered.
2. The number of sandwiches that can be ordered that involve turkey and mayonnaise.

In each case, you can use the fundamental counting principle to help.

1. A sandwich is made by choosing a bread, a meat, a vegetable, and a sauce. There are 5 outcomes for the event of choosing bread, 4 outcomes for the event of choosing meat, 12 outcomes for the event of choosing vegetables, and 3 outcomes for the event of choosing a sauce. The total number of sandwiches that can be ordered is: \begin{align*}5 \cdot 4 \cdot 12 \cdot 3=720\end{align*}
2. A sandwich with turkey and mayonnaise is made by choosing a bread, turkey, a vegetable, and mayonnaise. There are 5 outcomes for the event of choosing bread, there is 1 outcome for the event of choosing turkey, there are 12 outcomes for the event of choosing vegetables, and there is 1 outcome for the event of choosing mayonnaise. The total number of sandwiches with turkey and mayonnaise that can be ordered is: \begin{align*}5 \cdot 1 \cdot 12 \cdot 1=60\end{align*}

The probability of a sandwich with turkey and mayonnaise is \begin{align*}\frac{60}{720}=\frac{1}{12}\end{align*}.

#### Using Permutations

In your class of 35 students, there are 20 girls and 15 boys. There is a class competition and 1st, 2nd, and 3rd place winners are decided. What is the probability that all of the winners are boys?

In order to answer this probability question you need to know:

1. The total number of 1st, 2nd, 3rd place winners that can be chosen.
2. The number of 1st, 2nd, 3rd place winners that are all boys that can be chosen.

In each case, you are dealing with permutations, because the order of the people for 1st, 2nd, and 3rd place matters.

1. There are 35 students and 3 need to be chosen and arranged into 1st, 2nd, and 3rd place.

\begin{align*}_{35}P_3 &= \frac{35\!}{(35-3)!}=\frac{35!}{32!}=\frac{35 \cdot 34 \cdot 33 \cdot \bcancel{32 \cdot 31 \cdots 3 \cdot 2 \cdot 1}}{\bcancel{32 \cdot 31 \cdots 3 \cdot 2 \cdot 1}}\\ &= 35 \cdot 34 \cdot 33\\ &= 39270\end{align*}

2. There are 15 boys and 3 need to be chosen and arranged.

\begin{align*}_{15}P_3 &= \frac{15!}{(15-3)!}=\frac{15!}{12!}=\frac{15 \cdot 14 \cdot 13 \cdot \bcancel{12 \cdot 11 \cdots 3 \cdot 2 \cdot 1}}{\bcancel{12 \cdot 11 \cdots 3 \cdot 2 \cdot 1}}\\ &= 15 \cdot 14 \cdot 13\\ &= 2730\end{align*}

The probability of all boy winners is \begin{align*}\frac{2730}{39270} \approx 7\%\end{align*}.

Now, let's look at some problems involving combinations

In your class of 35 students, there are 20 girls and 15 boys. 5 students are chosen at random for a presentation. What is the probability that the group is made of all boys?

In order to answer this probability question you need to know:

1. The total number of groups that can be formed.
2. The number of groups with all boys.

In each case, you are dealing with combinations, because the order of the people for the presentation doesn't matter.

1. There are 35 students in the class and 5 to be chosen. The number of ways the 5 could be chosen are:

\begin{align*}_{35}C_5 = \frac{35!}{5!(35-5)!}=\frac{35!}{5!30!} &= \frac{35 \cdot 34 \cdot 33 \cdot 32 \cdot 31 \cdot \bcancel{30 \cdots 3 \cdot 2 \cdot 1}}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot \bcancel{30 \cdot 29 \cdot 28 \cdots 3 \cdot 2 \cdot 1}}\\ &= \frac{35 \cdot 34 \cdot 33 \cdot 32 \cdot 31}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\ &= \frac{38955840}{120}\\ &= 324632\end{align*}

2. There are 15 boys in the class and 5 boys to be chosen. The number of ways the 5 could be chosen are:

\begin{align*}_{15}C_5 =\frac{15!}{5!(15-5)!}=\frac{15!}{5!10!} &= \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\ &= \frac{360360}{120}\\ &= 3003 \end{align*}

The probability of an all boy group is \begin{align*}\frac{3003}{324632} \approx 0.9\%\end{align*}.

### Examples

#### Example 1

Earlier, you were given a problem on a standard deck of cards.

Suppose you draw two cards from a standard deck (one after the other without replacement) and record the results.

1. How many outcomes are there?
2. How many ways are there to choose an ace and then a four?
3. What is the probability that you choose an ace and then a four?

a) This is an example of a permutation, because the order matters. You are choosing 2 cards from a set of 52 cards.

\begin{align*}_{52}P_2=\frac{52!}{(52-2)!}=\frac{52!}{50!}=50 \cdot 51=2652\end{align*}

b) Choosing an ace and choosing a four are independent events. There are 4 aces and 4 fours. By the fundamental counting principle, there are \begin{align*}4 \cdot 4=16\end{align*} ways to choose an ace and then a four.

c) The probability that you choose an ace and then a four is \begin{align*}\frac{16}{2652} \approx 0.6\%\end{align*}.

#### Example 2

Calculate \begin{align*}_{10}P_4\end{align*} and \begin{align*}_{10}C_4\end{align*}. Interpret each calculation.

\begin{align*}_{10}P_4=\frac{10!}{(10-4)!}=\frac{10!}{6!}=10 \cdot 9 \cdot 8 \cdot 7=5040\end{align*}. This is the number of ways to choose and arrange four objects from a set of 10 objects.

\begin{align*}_{10}C_4=\frac{10!}{4!(10-4)!}=\frac{10!}{4!6!}=\frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1}=\frac{5040}{24}=210\end{align*}. This is the number of ways to choose four objects from a set of 10 objects.

#### Example 3

You are driving your friends to the beach in your car. Your car has room for 4 additional passengers besides yourself. You have 10 friends (not including yourself) going to the beach. In how many ways could the friends who will ride in your car be chosen?

This is a combination problem, because there is no indication that the order of the friends within the car matters. \begin{align*}_{10}C_4=210\end{align*} (from #1). There are 210 different combinations of 4 friends that could be chosen.

#### Example 4

Make up a probability question that could be solved with the calculation \begin{align*}\frac{_3C_2}{_{15}C_2}\end{align*}.

The total number of outcomes in the sample space is \begin{align*}_{15}C_2\end{align*}, which is the number of ways to choose 2 objects from a set of 15. The number of outcomes in the event that you are calculating the probability of is \begin{align*}_3C_2\end{align*}, which is the number of ways to choose 2 objects from a set of 3. Here is one possible question:

The math club has 15 members. 12 are upperclassmen and 3 are freshman. 2 members of the club need to be chosen to make a morning announcement. What is the probability that the 2 who are chosen are both freshmen?

### Review

Calculate each and interpret each calculation in words.

1. \begin{align*}_8P_2\end{align*}

2. \begin{align*}_8P_8\end{align*}

3. \begin{align*}_8C_8\end{align*}

4. \begin{align*}_{14}C_8\end{align*}

5. Will \begin{align*}_nP_k\end{align*} always be larger than \begin{align*}_nC_k\end{align*} for a given \begin{align*}n,k\end{align*} pair?

6. Your graphing calculator has the combination and permutation formulas built in. Push the MATH button and scroll to the right to the PRB list. You should see \begin{align*}nPr\end{align*} and \begin{align*}nCr\end{align*} as options. In order to use these: 1) On your home screen type the value for \begin{align*}n\end{align*}; 2) Select \begin{align*}nPr\end{align*} or \begin{align*}nCr\end{align*}; 3) Type the value for \begin{align*}k\end{align*} (\begin{align*}r\end{align*} on the calculator). Use your calculator to verify that \begin{align*}_{10}C_5=252\end{align*}.

First, state whether each problem is a permutation or combination problem. Then, solve.

7. Suppose you need to choose a new combination locker. You have to choose 3 numbers, each different and between 0 and 40. How many choices do you have for the combination? If you choose at random, what is the probability that you choose 0, 1, 2 for your combination?

8. You just won a contest where you can choose 2 friends to go with you to a concert. You have five friends (Amy, Bobby, Jen, Whitney, and David) who are available and want to go. If you choose two friends at random, what is the probability that you choose Bobby and David?

9. There are 12 workshops at a conference and Michael has to choose 4 to attend. In how many ways can he choose the 4 to attend?

10. 10 girls and 4 boys are finalists in a contest where 1st, 2nd, and 3rd place winners will be chosen. What is the probability that all winners are boys?

11. Using the information from the previous problem, what is the probability that all winners are girls?

12. You visit 12 colleges and want to apply to 4 of them. 5 of the colleges are within 100 miles of your house. If you choose the colleges to apply to at random, what is the probability that all 4 colleges that you apply to are within 100 miles of your house?

13. For the 12 colleges you visited, you rank your top five. In how many ways could you do this? Your friend Jesse randomly tries to guess the five colleges that you choose and the order that you ranked them in. What is the probability that he guesses correctly?

14. For the special at a restaurant you can choose 3 different items from the 10 item menu. How many different combinations of meals could you get? If the waiter chooses your 3 items at random, what's the probability that you get the soup, the salad, and the pasta dish?

15. In a typical poker game, each player is dealt 5 cards. A royal flush is when the player has the 10, Jack, Queen, King, and Ace all of the same suit. What is the probability of a royal flush? Hint: How many 5 card hands are there? How many royal flushes are there?

To see the Review answers, open this PDF file and look for section 11.8.

### Notes/Highlights Having trouble? Report an issue.

Color Highlighted Text Notes

### Vocabulary Language: English

!

The factorial of a whole number $n$ is the product of the positive integers from 1 to $n$. The symbol "!" denotes factorial. $n! = 1 \cdot 2 \cdot 3 \cdot 4...\cdot (n-1) \cdot n$.

combination

Combinations are distinct arrangements of a specified number of objects without regard to order of selection from a specified set.

decision chart

A decision chart is a tree-shaped sequence of numbers used to determine the probability of occurrence of a given event.

Event

An event is a set of one or more possible results of a probability experiment.

factorial

The factorial of a whole number $n$ is the product of the positive integers from 1 to $n$. The symbol "!" denotes factorial. $n! = 1 \cdot 2 \cdot 3 \cdot 4...\cdot (n-1) \cdot n$.

Fundamental Counting Principle

The Fundamental Counting Principle states that if an event can be chosen in p different ways and another independent event can be chosen in q different ways, the number of different arrangements of the events is p x q.

Independent Events

Two events are independent if the occurrence of one event does not impact the probability of the other event.

Permutation

A permutation is an arrangement of objects where order is important.

Sample Space

In a probability experiment, the sample space is the set of all the possible outcomes of the experiment.