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 outcomes, the 2nd activity has m possible outcomes, then the total number of possible outcomes is mn.
So, if you have 4 pairs of slacks and 3 warm shirts, you have a total of 12 different shirt and slacks combinations to choose from when you get dressed.

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! = n % (n – 1) % (n – 2) % ..... 3 % 2 % 1

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 Permutations and Choose to refer to Combinations

(we often call them perms and coms).

Definition:

A Permutation, denoted n P r , is an ordered arrangement of a group of
r objects taken from a set of n distinct objects.

The important words here are ordered and a group.

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 a group of r objects
taken from a set of n distinct objects without regard to order.

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 n, than there are permutations. This means that the formula for n C r. has to give us a smaller number than that for n P r.. When we analyse the formula, we see that n C r is just n P r. divided by r ! since there are r ! ways to arrange the r elements of the group in order -- and with combinations, order doesn't matter.

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 binomial coefficients since they are the coefficients of the terms in the expansion of ( a + b ) n , so they're also the numbers which make up Pascal's Triangle.

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 = n C ( n – 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 75 C 3 .

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
\$ 5 C 3 \$ 4 C 2 = 1260.

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! / 17TRUE e) TRUE 2! = 2 f) FALSE: it = 36 g) TRUE h) 4! + 0! = 25TRUE: 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 C 2 = 1200 ways -- we use Choose since order doesn't matter. It's combinations.

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 \$ 2 C 1 = 90 ways to choose 2 good batteries and 1 defect.

c) Now we want him to choose both defects so he takes only 1 good one:
there are 10 C 1 \$ 2 C 2 = 10 ways to choose 1 good battery and 2 defects.

6)

 a) 13 C 2 = 78 ways b) 24 C 5 = 42, 504 ways

.

.

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