11.1 - Permutations and Combination

11.1 - Permutations and Combination

The Fundamental Counting Principle

If there are n items and $m_1$  ways to select  first item and  $m_2$  ways to select a second item after the first has been chosen, and so on, then there are  $m_1\cdot m_2\cdot...\cdot m_n$  ways to select n items.

An example

• At a sandwich shop you can select from four types of bread, five types of meat, and three types of cheese. How many sandwich choices are there?

•  $4\cdot5\cdot3=60$  

• There are 60 different ways to create a sandwich at this shop.

Permutation

A selection of a group of objects in which the order matters.

An example

• Six students are running a race. In how many different orders can they cross the finish line?

• Any of the six can finish first, then there are five other kids who could possibly finish second, and after two have already crossed the finish line four are still on the course who could finish third, and so forth.

•  $6\cdot5\cdot4\cdot3\cdot2\cdot1=720\$  different ways

The permutation of n items is n!

Which we read as "n factorial". 

 $n!\ =\ n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdot\left(n-3\right)\cdot...\cdot1$ 

So 4! = 4*3*2*1 = 24 

It's possible we might not want to put all the items of a set in order.

As an example, in that footrace with six kids, how many different ways can three students finish first, second, and third?

6*5*4 = 120 different ways.

Another way to think about it:

• How many ways can we put 6 things in order, divided by the number of ways we can put the last three things in order (because we're not worried about their order, just the top three)

•  $\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1}$  

• You can divide the top and bottom of the fraction by 3*2*1

As a formula:

• The number of permutations of n items taken r at a time is  $n\Pr=\frac{n!}{\left(n-r\right)!}$  

• So the number of permutations of 7 items taken 3 at a time is  $7P3=\frac{7!}{\left(7-3\right)!}=\frac{7!}{4!}$  

You try

Open Ended

A club at school has 12 members. In how many different ways can the club select a president, vice-president, and secretary?

What if the order does not matter?

Say you are doing a cleanup project and you need to select three classmates for your team. The order does not matter, they are the same three kids any way to pick them.

If order does not matter, we call it a combination

• So let's look at that cleanup problem. There's 28 kids in your class and you are going to draw three names to be on your crew. In how many ways could you pick three classmates to work with?

We recognize 28*27*26, but the order doesn't matter. Any group of three kids counts as one grouping.

• So we have to divide by the number of ways we can arrange 3 people.

•  $\frac{28\cdot27\cdot26}{3\cdot2\cdot1}=\frac{19656}{6}=3276$  

As a formula

 $nCr=\frac{n!}{r!\left(n-r\right)!}$  

It's the permutation formula, divided by the number of ways I can arrange the things in the selected group.

You try

Open Ended

You have 25 movies in your Netflix list. You are going on a college visit and think you will have time to watch four of them in the car. How many ways can you select 4 movies from a group of 25 if order does not matter?

Let's practice

Multiple Choice

Find the number of possibilities:
A team of 17 softball players needs to choose three players to refill the water cooler.

• 272
• 4080
• 680

Multiple Choice

Which of the following is an example of combination?

• Form a passcode with 4 digits

• Students line up in a queue to assembly

• Choose 4 students in a class committee

• Choose the chairperson, secretary and treasurer in a club

Multiple Choice

Grant has five pairs of pants, nine shirts, and six ties. How many different outfits can he make consisting of one pair of pants, one shirt, and one tie?

• 45

• 270

• 30

• 54

Multiple Choice

There are 18 people running in a cross country race. How many possible ways are there to place the runners in first, second, and third?

• 324

• 4896

• 816

• 54

Multiple Choice

Indiana license plates have 3 letters followed by 3 numbers. Assuming no combinations of letters or numbers are excluded, how many can be made?

• 15,600,000

• 156,000

• 100,000,000

• 100,000

Multiple Choice

How many ways can you choose a manager and assistant from a 9-person task force?

• 81

• 18

• 72

• 9

Multiple Choice

Members of 6 different school organizations decorated floats for the homecoming parade. How many different ways can first, second, and third prize be awarded?

• 18

• 120

• 36

• 18

Multiple Choice

Determine whether the following scenarios are a permutation or a combination:

Selecting a lead and an understudy for a school play.

• Combination

• Permutation