Counting Posibilities: Permutations & Combinations |

**Intro to Counting Possibilities**

Since a study of the branch of math known as **statistics** was first undertaken by gamblers

who wanted to know the possible outcomes in their games of chance,

it deals with counting possibilities and predicting the probability of specific **outcomes** or **events** using mathematical principles. For instance, if a gambler shooting craps (a dice game)

needs to know the probability of rolling 7 -- three times consecutively, he would first have

to know what and how many combinations on the dice add to 7.

Before we can discuss probability, we must know how to count possibilities since the

probability of an event depends on the number of possible ways for the event to occur.

This lesson covers counting principles: methods prerequisite to a discussion of probability.

.

**The Multiplication Principle**

If in a compound experiment, the** first activity has n **possible

So, if you have

If a diner menu offers 4 choices of soup, 3 different entrées, and 5 lunchtime specials, there are

**4 ****%**** 3 ****%**** 5 or 60** different possible **combinations** for a meal.

It's pretty obvious that we wouldn't want to have to list all these possibilities -- besides, we don't need a list of them, we just need to know how many there are -- we just need the count. That's where permutations and combinations come in.

.

**Factorials!**

Let's consider the number of ways there are to arrange 5 books on a shelf if their order doesn't matter. We have 5 choices for the first book we place, 4 for the next, 3, then 2 and finally there's only 1 book left to place on the shelf. This says that there are **5** **%**** 4** **%**** 3** **%**** 2** **%**** 1** or 120 different ways to place the books. This number denoted 5! is called 5 **factorial** . It is the **product** of all the positive integers or counting numbers, starting at 1, ending at 5.

We use **!** (the exclamation mark) to denote **factorial**.

**definition:**

** n!** =

It is the product of the positive integers less than or equal to *n*, so **3!** = **3**** %**** 2** **%**** 1**

By **definition**, we set **0! = 1**

**Note:** **5! = 5** **%**** 4** **%**** 3** **%**** 2** **%**** 1**, and **3!** = **3**** %**** 2** **%**** 1**, so when we divide 5! by 3! we get **5** **%**** 4**, since the **3**** %**** 2** **%**** 1** cancels out. This can be generalized to:

In our example, *n* = 5 and ( *n – r* ) = 3, which makes ( *n – r* + 1) = 4.

The result is **5** **%**** 4** since the last term in the product is ( *n – r* + 1).

.

**Permutations and Combinations**

**Hint:** use ** Pick** to refer to

(we often call them *perms* and *coms*).

**Definition:**

A** Permutation**, denoted ** _{n }P_{ r}** , is an

The important words here are ** ordered** and

Here are all the permutations of the 5 vowels taken 2 at a time:

*ae ai ao au ea ei eo eu ia ie
io iu oa oe oi ou ua ue ui uo*

Since there are 5 vowels and we're selecting 2 of the 5, *r* = 2 and *n* = 5.

_{5 }**P _{ }**2 = 20

There are 20 permutations -- because order matters, so ** ae and ea are not the same**.

We have 5 choices for the 1st vowel, then we have 4 choices for the 2nd to make 20 choices.

To generalize a formula for the number of different permutations of *n* objects taken *r* at a time, we use the multiplication principle.

It says that we have *n* choices for the 1st **pick**, (*n – 1*) choices for the 2nd **pick**, and so on until we have (*n – r + 1*) choices for the last pick. This product is simply the quotient of *n*! and (*n – r*)! shown in the previous section on factorials. This then is the formula for ** _{n }P_{ r}** .

**Note:** A good way to remember that **order matters for perms** is to recall that a "Combination Lock" should be called a PERMUTATION LOCK . If you dial in the right numbers in the wrong order, the lock won't open so order matters!

**Examples:**

The number of ways to pick 1st, 2nd and 3rd prize winners from 15 finalist paintings is

_{15 }**P _{ }**3 = (15!) / (15 – 3)! = 2730.

The number of ways to pick a president, vice-president, treasurer and secretary from

52 union members is _{52 }**P _{ }**4 = (52!) / (52 – 4)! = 6, 497, 400.

The number of ways to pick the 6 winning lotto numbers from 49 is

_{49 }**P _{ 6}** = (49!) / (49 – 6)! = 10, 068, 300, 000.

This means that the chance of winning the jackpot is 1 out of 10, 068, 300, 000

.

**calculator hint:** on the TI-83 series we find the *perms* and *coms* functions in the MATH menu. We enter the value for *n*, then choose MATH -- PRB -- select #2 for perms, or #3 for coms -- then enter the value for *r*. We can do it with the CATALOG menu, but it's slower.

**Definition:**

A** Combination**, denoted ** _{n }C_{ r}** or , is an arrangement of

taken from a set of

Now, we consider 1-2-3 to be the same as 3-2-1 or 2-1-3 etc. They are **all the same combination**. However they are **3 different permutations**. So obviously, there are always **fewer combinations** of ** r** objects from

When we analyse the formula, we see that ** _{n }C_{ r}** is just

In the example above, there are 3! or 6 ways to arrange the numbers 1, 2, and 3. This means there are 6 **permutations** of 1-2-3 but they only count as a single combination.

So, there are 10 **combinations** of the 5 vowels taken 2 at a time. They are:

*ae ai ao au ei eo eu io iu ou*

**Note:** the values of ** _{n }C_{ r} **are referred to as

**Note:** There are as many ways to choose *r* objects from *n* objects as there are to leave ( *n – r *) objects, so we can say that ** _{n }C_{ r}** =

For example, if we choose 3 objects from 5, it's the same as leaving 2 objects unchosen. This formula helps to make calculations easier when using your head instead of your calculator. Since that happens rarely, we can just enter ** _{75 }C_{ 72}** in our calculators to get the answer. If we're calculating with our minds, we would find

**Examples:**

The number of ways to choose 3 CD's from the top 10 sellers is _{10 }**C _{ }**3 = 120.

The number of ways to choose a committee of 4 people from 60 people is _{60 }**C _{ }**4 = 487,635.

The number of ways to choose 2 math, 3 physics and 2 history teachers from 7 math, 5 physics

and 4 history applicants is _{7 }**C _{ }**2 $

The **probability** **of **choosing **any** given **combination** of *r* objects **is**

**1 over the total** number of **possibilities**.

.

**Practice**

1) State whether these statements are True or False:

a) 20! = 20 $ 19 $ 18! | b) 3! + 4! = 7! | c) 4! $ 3! = 12! | d) 16! = 17! / 17 |

e) | f) | g) | h) 4! + 0! = 25 |

2) In how many different ways can the 8 horses in a race come first, second and third?

3) In how many different ways can we buy 3 of 15 different postcards on the rack?

4) A company needs to hire 3 secretaries from 10 applicants as well as

2 bookkeepers from 5 applicants. In how many different ways can they do this?

5) A box of 12 batteries contains 2 defective ones.

In how many different ways can an inspector choose 3 of the batteries and:

a) get none of the defects | b) get one of the defects | c) get both of the defects |

6) Calculate the number of ways that:

a) a developer can choose 2 of 13 sites to build a new store.

b) 5 of 24 tax returns can chosen to be audited.

.

**Solutions**

1) State whether these statements are True or False:

a) 20! = 20 $ 19 $ 18! this is TRUE |
b) 3! + 4! = 7! 6 + 24 ! 7! FALSE |
c) 4! $ 3! = 12! 24(6) ! 12! FALSE |
d) 16! = 17! / 17 TRUE |

e) TRUE 2! = 2 |
f) FALSE: it = 36 |
g) TRUE |
h) 4! + 0! = 25 TRUE: 4! = 24, 0! = 1 |

2) _{8 }**P _{ }**3 = 336 ways -- we use Pick since order matters. It's permutations.

3) _{15 }**C _{ }**3 = 455 ways -- we use Choose since order doesn't matter. It's combinations.

4) _{10 }**C _{ 3}** $

5)

a) Since there are 2 defects, there are 10 good batteries from which he chooses 3

so there are _{10 }**C _{ 3}** or 120 ways to choose 3 good batteries and no defects.

b) Now he has to choose 2 good ones and 1 defect so there are

** _{10 }C_{ 2}** $

c) Now we want him to choose both defects so he takes only 1 good one:

there are ** _{10 }C_{ 1}** $

6)

a) = 78 ways_{13 }C_{ 2} |
b) = 42, 504 ways_{24 }C_{ 5} |

.

.

*(all content of the MathRoom Lessons **© Tammy the Tutor; 2002 - ?).*