<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />
You are viewing an older version of this Concept. Go to the latest version.

# 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
Progress
Estimated13 minsto complete
%
Counting with Permutations and Combinations

Sometimes it makes sense to count the number of ways for an event to occur by looking at each possible outcome. However, when there are a large number of outcomes this method quickly becomes inefficient. If someone asked you how many possible regular license plates there are for the state of California, it would not be feasible to count each and every one. Instead, you would need to use the fact that on the typical California license plate there are four numbers and three letters. Using this information, about how many license plates could there be?

#### Watch This

http://www.youtube.com/watch?v=qJ7AYDmHVRE James Sousa: The Counting Principle

#### Guidance

Consider choice  $A$ with three options  $(A_1,A_2,A_3)$ and choice  $B$ with two options $(B_1,B_2)$ . If you had to choose an option from  $A$ and then an option from $B$ , the overall total number of options would be $3 \cdot 2=6$ . The options are $A_1B_1,A_1B_2,A_2B_1,A_2B_2,A_3B_1,A_3B_2$ .

You can see where the six comes from by making a decision chart and using the Fundamental Counting Principle. First, determine how many decisions you are making. Here, there are only two decisions to make (1: choose an option from $A$ ; 2: choose an option from $B$ ), so you will have two “slots” in your decision chart. Next, think about how many possibilities there are for the first choice (in this case there are 3) and how many possibilities there are for the second choice (in this case there are 2). The Fundamental Counting Principle says that you can multiply those numbers together to get the total number of outcomes.

Another type of counting question is when you have a given number of objects, you want to choose some (or all) of them, and you want to know how many ways there are to do this. For example, a teacher has a classroom of 30 students, she wants 5 of them to do a presentation, and she wants to know how many ways this could happen. These types of questions have to do with combinations and permutations. The difference between combinations and permutations has to do with whether or not the order that you are choosing the objects matters.

• A teacher choosing a group to make a presentation would be a combination problem, because order does not matter.
• A teacher choosing 1 st , 2 nd , and 3 rd place winners in a science fair would be a permutation problem, because the order matters (a student getting 1 st place vs. 2 nd place are different outcomes).

Recall that the factorial symbol, !, means to multiply every whole number up to and including that whole number together. For example, $5!=5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ . The factorial symbol is used in the formulas for permutations and combinations.

Combination Formula: The number of ways to choose  $k$ objects from a group of  $n$ objects is --

$_nC_k=\dbinom{n}{k}=\frac{n!}{k! \left(n-k\right)!}$

Permutation Formula: The number of ways to choose and arrange   $k$ objects from a group of  $n$ objects is --

$_nP_k=k!\dbinom{n}{k}=k! \cdot \frac{n!}{k!\left(n-k\right)!}=\frac{n!}{\left(n-k\right)!}$

Notice that in both permutation and combination problems you are not allowed to repeat your choices. Any time you are allowed to repeat and order does not matter, you can use a decision chart. (Problems with repetition where order does not matter are more complex and are not discussed in this text.)

Whenever you are doing a counting problem, the first thing you should decide is if the problem is a decision chart problem, a permutation problem, or a combination problem. You will find that permutation problems can also be solved with decision charts. The opposite is not true. There are many decision chart problems (ones where you are allowed to repeat choices) that could not be solved with the permutation formula.

Note: Here you have only begun to explore counting problems. For more information about combinations, permutations, and other types of counting problems, consult a Probability text.

Example A

You are going on a road trip with 4 friends in a car that fits 5 people. How many different ways can everyone sit if you have to drive the whole way?

Solution: A decision chart is a great way of thinking about this problem. You have to sit in the driver’s seat. There are four options for the first passenger seat. Once that person is seated there are three options for the next passenger seat. This goes on until there is one person left with one seat.

$1 \cdot 4 \cdot 3 \cdot 2 \cdot 1=24$

Example B

How many different ways can the gold, silver and bronze medals be awarded in an Olympic event with 12 athletes competing?

Solution: Since the order does matter with the three medals, this is a permutation problem. You will start with 12 athletes and then choose and arrange 3 different winners.

$_{12}P_3=\frac{12!}{\left(12-3\right)!}=\frac{12!}{9!}=\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot \ldots}{9 \cdot \ldots}=12 \cdot 11 \cdot 10=1320$

Note that you could also use a decision chart to decide how many possibilities are there for gold (12) how many possibilities are there for silver (11 since one already has gold) and how many possibilities are there for bronze (10). You can use a decision chart for any permutation problem.

$12 \cdot 11 \cdot 10=1320$

Example C

You are deciding which awards you are going to display in your room. You have 8 awards, but you only have room to display 4 awards. Right now you are not worrying about how to arrange the awards so the order does not matter. In how many ways could you choose the 4 awards to display?

Solution: Since order does not matter, this is a combination problem. You start with 8 awards and then choose 4.

$_8C_4=\dbinom{8}{4}=\frac{8!}{4!\left(8-4\right)!}=\frac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1}=7 \cdot 2 \cdot 5=70$

Note that if you try to use a decision chart with this question, you will need to do an extra step of reasoning. There are 8 options I could choose first, then 7 left, then 6 and lastly 5.

$8 \cdot 7 \cdot 6 \cdot 5=1680$

This number is so big because it takes into account order, which you don’t care about. It is the same result you would get if you used the permutation formula instead of the combination formula. To get the right answer, you need to divide this number by the number of ways 4 objects can be arranged, which is $4!=24$ . This has to do with the connection between the combination formula and the permutation formula.

Concept Problem Revisited

A license plate that has 3 letters and 4 numbers can be represented by a decision chart with seven spaces. You can use a decision chart because order definitely does matter with license plates. The first spot is a number, the next three spots are letters and the last three spots are numbers. Note that when choosing a license plate, repetition is allowed.

$10 \cdot 26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10=26^3 \cdot 10^4=175,760,000$

This number is only approximate because in reality there are certain letter and number combinations that are not allowed, some license plates have extra symbols, and some commercial and government license plates have more numbers, fewer letters or blank spaces.

#### Vocabulary

A combination is the number of ways of choosing  $k$ objects from a total of  $n$ objects (order does not matter).

A permutation is the number of ways of choosing and arranging  $k$ objects from a total of  $n$ objects (order does matter)

A decision chart is a sequence of numbers that multiply together where each number represents the number of possible options for that slot.

#### Guided Practice

1. There are 20 hockey players on a pro NHL team, two of which are goalies. In how many different ways can 5 skaters and 1 goalie be on the ice at the same time?

2. In how many different ways could you score a 70% on a 10 question test where each question is weighted equally and is either right or wrong?

3. How many different 4 digit ATM passwords are there? Assume you can repeat digits.

1. The question asks for how many on the ice, implying that order does not matter. This is combination problem with two combinations. You need to choose 1 goalie out of a possible of 2 and choose 5 skaters out of a possible 18.

$\dbinom{2}{1}\dbinom{18}{5}=2 \cdot \frac{18!}{5! \cdot 13!}=17136$

2. The order of the questions you got right does not matter, so this is a combination problem.

$\dbinom{10}{7}=\frac{10!}{7!3!}=120$

3. Order does matter. There are 10 digits and repetition is allowed. You can use a decision chart for each of the four options.

$10 \cdot 10 \cdot 10 \cdot 10=10,000$

#### Practice

Simplify each of the following expressions so that they do not have a factorial symbol.

1. $\frac{7!}{3!}$

2. $\frac{110!}{105!5!}$

3. $\frac{52!}{49!}$

4. In how many ways can you choose 3 objects from a set of 9 objects?

5. In how many ways can you choose and arrange 4 objects from a set of 15 objects?

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

6. Suppose you need to choose a new combination for your combination lock. You have to choose 3 numbers, each different and between 0 and 40. How many combinations are there?

7. You just won a contest where you can choose 2 friends to go with you to a concert. You have five friends who are available and want to go. In how many ways can you choose the friends?

8. You want to construct a 3 digit number from the digits 4, 6, 8, 9. How many possible numbers are there?

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

10. 9 girls and 5 boys are finalists in a contest. In how many ways can 1 st , 2 nd , and 3 rd place winners be chosen?

11. 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?

12. You visit 12 colleges and want to apply to 4 of them. In how many ways could you choose the four to apply to?

13. For the 12 colleges you visited, you want to rank your top five. In how many ways could you rank your top 5?

14. Explain why the following problem is not strictly a permutation or combination problem : The local ice cream shop has 12 flavors. You decide to buy 2 scoops in a dish. In how many ways could you do this if you are allowed to get two of the same scoop?

15. 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  ${_nP}_r$ and  $_nC_r$ as options. In order to use these: 1) On your home screen type the value for $n$ ; 2) Select  ${_nP}_r$ or $_nC_r$ ; 3) Type the value for  $k$ ( $r$ on the calculator). Use your calculator to verify that ${_{10}C}_5=252$ .

### 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

combination

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

decision chart

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

Event

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

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

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

Independent Events

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

Permutation

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

Sample Space

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