10.1 Apply the Counting Principle and Permutations

 

 

VOCABULARY

Permutation

A permutation is an ordering of n objects.

 

Factorial

Represented by the symbol !, n factorial is defined as:
n! = n · {n - 1) · {n - 2) ·.....·3 · 2 · 1.

 

FUNDAMENTAL COUNTING PRINCIPLE

Two Events If one event can occur in m ways and another event can occur in n ways, then the number of ways that both events can occur is __m · n__ .

 

Three or More Events The fundamental counting principle can be extended to three or more events. For example, if three events occur in m, n, and p ways, then the number of ways that all three events can occur is __m · n · p__.

 

Example 1

Use the fundamental counting principle

 

Pizza You are buying a pizza. You have a choice of 3 crusts, 4 cheeses, 5 meat toppings, and 8 vegetable toppings. How many different pizzas with one crust, one cheese, one meat, and one vegetable can you choose?

 

Solution

Use the fundamental counting principle to find the total number of pizzas. Multiply the number of crusts ( _3_ ), the number of cheeses ( _4_ ), the number of meats ( _5_ ), and the number of vegetables ( _8_ ).

 

Number of pizzas = 3 · 4 · 5 · 8 = 480

 

 

Example 2

Use the counting principle with repetition

 

Telephone Numbers A town has telephone numbers that all begin with 329 followed by four digits. How many different phone numbers are possible (a) if numbers can be repeated and (b) if numbers cannot be repeated?

 

a.        There are _10_ choices for each digit. Use the fundamental counting principle to find the total amount of phone numbers.

Phone numbers = 10 · 10 · 10 · 10 = 10,000

b.        If you cannot repeat digits, there are still _10_ choices for the first number, but then only _9_ remaining choices for the second digit, _8_ choices for the third digit, and _7_ choices for the fourth digit. Use the fundamental counting principle.

Phone numbers = 10 · 9 · 8 · 7 = _5040_

Example 3

Find the number of permutations

Playoffs Eight teams are competing in a baseball playoff.

a.      In how many different ways can the baseball teams finish the competition?

b.      In how many different ways can 3 of the baseball teams finish first, second, and third?

 

Solution

a.      There are 8! different ways that the teams can finish. 8! = 8 · 7 · 6 · 5 · 4 · 3 · 2 ·1
= 40,320

b.      Any of the _8_ teams can finish first, then any of the _7_ remaining teams can finish second, and then any of the remaining 6 teams can finish third._8 · 7 · 6_ = __336_

 

 

PERMUTATIONS OF n OBJECTS TAKEN r AT A TIME

 

The number of permutations of r objects taken from a group of n distinct objects is denoted by nPr

 

 


Example 4

Find permutations of n objects taken rat a time

 

Homework You have 6 homework assignments to complete over the weekend. However, you only have time to complete 4 of them on Saturday. In how many orders can you complete 4 of the assignments?

 

Solution

6
 
Find the number of permutations of 6 objects taken 4 at a time.

!                      !

6 -4
 

2
 

720
 

2
 

6
 
6P4 =                         =                   =                    = _360_

(                 )!                  !

You can complete the 4 assignments in _360_ different orders.

 

 

 

 

PERMUTATIONS WITH REPETITION

The number of distinguishable permutations of n objects where one object is repeated s± times, another is repeated s2 times, and so on, is:

 

 


Example 5

Find permutations with repetition

 

Find the number of distinguishable permutations of the letters in (a) EVEN and (b) CALIFORNIA.

 

Solution

a.  

24
 
EVEN has _4_ letters of which _E_ is repeated _2_ times. So, the number of distinguishable

4
 
!

2
 

2
 
permutations is                  =                   = _12_

!