__Permutations and Combinations__

Ooo...wow...sounds fancy you think (or maybe you don't, but I say you do)...

First off, what *is* a permutation?

Well, a permutation is an arrangement of a
group things **in a particular order**.

So then, what is a combination?

A combination is an arrangement of a group
of things **when order does not matter**.

First let's talk about something different though, which
incorporates neither word (*so* evil)...

THE COUNTING PRINCIPLE

This basically says if there are **x**
ways to do one thing, and **y **ways to do another, then there are **x * y**
ways to do both.

For example, I want to make a pizza. There are 2 different types of cheese I can have, and 4 different toppings. Assuming I can only have 1 of each on my pizza, how many combinations are there?

2 * 4 = 8 pizzas

Now, we can prove this by making a list or diagram...say the
cheeses are mozzarella (M) and cheddar (C).

The toppings are pepperoni (P), anchovies (A), broccoli (B), and mushrooms (M2).

Let's make a list:

We have:

MP, MA, MB, MM2

CP, CA, CB, CM2

Count them and there are 8. You can think of it as there are 4 toppings for each cheese, and 2 cheeses. Anyway, another example.

From New York City to Chicago there are 5 routes, from Chicago to Detroit there are 2, and from Detroit to Canada there are 3. If I want to stop in each place, how many ways are there for me to get from New York to Canada.

5 * 2 * 3 = 30 ways

You're not going to want to list 30 ways, so you can just use this. Get the picture?

If you do, good. If not, make up some problems and do them. Then check by listing the possibilities in an organized manner.

----------

Now on to permutations. First we should talk about a word
called **factorial** (not to be confused with factor, like my class seemed to
*_*). Factorial is the product of a all the numbers
from a given integer down to one. The symbol is !

So...it is n!

Let's say the n is 3...we have 3! (read three factorial).

We multiply every integer from three down to one.

3 * 2 * 1 = 6

3! = 6

What about 4!

4 * 3 * 2 * 1 = 24

4! = 24

You can see that getting from 4! to 3! is "taking
away" the 4 (dividing by 4)...

2! = 2 * 1 = 2...that is basically dividing 3! by 3...dividing 2! by 2 will get
you 1! (2/2 = 1)...

So 0!...what is it?

1 / 1 = 1...that's right...0! = 1...and you can't have a negative factorial.

However, I digress.

Say you have the numbers 1, 2, 3, 4, and 5, and you want to make 5-digit numbers. You can only use each digit once, and you want to know how many you can make.

Think about it...

These are the places: _ _ _ _ _

For the first place, there are 5 possibilities.

Let's stick a 2 in there: 2 _ _ _ _

For the second place there are 4 possibilities because 1 of the numbers has been
used.

Let's put in a 4: 24 _ _ _

Now for the third place there are only 3 possibilities, because 2 numbers have
been used...

We put in a 3: 243_ _

For the fourth place we have 2...

2431_

For the fifth place we have 1...

24315

Now to find out how many numbers there are, we use the counting
principle...5 * 4 * 3 * 2 * 1, or 5!

5! = 120...there are 120 numbers

What if we have 4 cards, one for each suit. We want to
arrange them in different orders of 4 cards.

Thinking to the last example, we can skip all the hard steps and go straight to
using factorial. This will be 4!, or 4
* 3 * 2 * 1 = 24 orders.

But, what if we wanted to make arrangements of...dum dum dum...2 cards...

Then we would have 4 possibilities for the
1st card and 3 for the second card...Counting Principle says to do

4 * 3, and that makes 12 orders.

This hard stuff can be skipped too. Now we use a fancier
permutation...P

We would write it _{4}P_{2} and it is read "the permutation
of 4 things taken 2 at a time."

(4! would be written _{4}P_{4} and read "the permutation of
4 things taken 4 at a time.")

Basically a permutation is written _{n}P_{r.
}This means to multiply n * (n-1) * (n-2)... to r factors of n!.

So 4 * (4-1) = 4 * 3 = 12

You see we only multiplied n * (n-1) because r was only 2.

Another example...how many 3 digit numbers can you make using 1, 2, 3, 4, 5, and 6 when no digit is repeated?

_{6}P_{3} = 6 * (6-1) *
(6-2) = 6 * 5 * 4 = 120 ways

Now let's say a digit can be
repeated. We can no longer use this permutation. Instead, let's use
the counting principle, saying that there are 6 possibilities for the the first
digit, 6 for the second, and 6 for the third. This is 6 * 6 * 6 = 216

(aka. 6^{3} = 216)

Click here*
*for the next page of permutations and combinations.

Click here to go back to the index.