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:
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...
For the fifth place we have 1...
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
We would write it 4P2 and it is read "the permutation of 4 things taken 2 at a time."
(4! would be written 4P4 and read "the permutation of 4 things taken 4 at a time.")
Basically a permutation is written nPr.
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?
6P3 = 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. 63 = 216)
for the next page of permutations and combinations.
Click here to go back to the index.