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 ₄P₂ and it is read "the permutation of 4 things taken 2 at a time."
(4! would be written ₄P₄ and read "the permutation of 4 things taken 4 at a time.")

Basically a permutation is written _nP_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?

₆P₃ = 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³ = 216)

Click here for the next page of permutations and combinations.
Click here to go back to the index.