College Algebra: Solving Permutation Problems

This lesson has not been reviewed.

Please purchase the lesson to review.

Helped tremendously with my GMAT

11/19/2008

~ ht1979

This lesson and Professor Burger's lesson on solving combinations helped me to finally understand both combination and permutation problems. Sure enough, these showed up on my GMAT, and I'm confident that I got them completely right (and quickly)! Thank you, professor Burger!

• Comment on this lesson!
• View all lesson comments »

I thought I’d say a couple of things about just figuring out the likelihood of certain events. In fact, the real truth of the matter is that we don’t know what’s going to happen tomorrow. So, how can you measure uncertainty? How can you measure things that you just don’t know? Well, the answer is that the mathematical theory of probability actually gives you the means of putting a measurement of likelihood to events that you just don’t know about. Either something that’s just not know, or not knowable, or something that hasn’t happened yet.
Anyway, to this end what we first have to start doing is just figuring out how to count carefully. Sometimes these things are called combinations, permutations. People that actually count are sometimes called “combinataurus.” These are just different ways of adding and counting and seeing things. You see what you’re counting is real easy. It turns out counting is actually not that easy. It’s a lot harder than you may think.
So, I thought we’d start off with just a simple example. Let’s just think about, for example, if I had three things and I wanted to count all the different ways that I can order those three things. So, I’ve got a block here, a block here and a block here. I want to see how many different ways there are just of ordering them, writing these three things out in different orders. Well, I can write it this way. So, I can write it as blue, yellow, green. In fact, let me actually make a little chart here of different ways of doing it. Let’s see if we can list them all.
So, there’s blue, yellow, green. Then I could switch these two and I would have blue, green, yellow. That’s a different ordering. Then I could go back to the first ordering, which is the same, but now put the yellow in front. That’s a different one. That’s yellow, blue, green. Now what I could do is switch these two and I would have yellow, green, blue. Well, what else could I do? Are there other combinations that I could possibly have here? Absolutely, I could put green first and I could have green, yellow, blue. Then I could switch these and report green, blue, yellow. Now, is there anything else I can do?
Well, actually I think those are all the combinations I can possibly can. All the ways of ordering these things I possibly can. We just sort of scramble them up, sort of a random order. Just write them down and see if we’ve got it covered. Do we have green, yellow and blue? Green, yellow, blue, it’s right there. If I mix them up a little bit. Like one of those games where you just shuffle them up a little bit. Like right there. How about that? That’s green, blue, yellow. Green, blue, yellow is here. What if I shuffle up a little more, like this way? That would be blue, yellow, green. Blue, yellow, green.
So, in fact, all of them really are here. So, there’s one, two, three, four, five, six, ways of actually reordering these things. That’s actually sort of hard to count, all the different ways of ordering these things. But if you think about it we can figure out a formula for it. Because there are three places I could possibly put the blue. Here, here or here. So, there’s three ways. But once I make that decision how many possibilities are there for the yellow. Well, only two left. The two that remain after I put the blue down. Then once I put that down the green, there’s no choice. The green will go in the left over spot.
So, how many possibilities are there total? Well, there are three for the first one, three possibilities. Then there’s two for the second one and there’s no possibilities for the last. This is a certainty. So, how many are there total? Well, there’s three and for each of the three I have two choice. So that’s actually 3 x 2 x 1. In fact, that’s just a factorial. So, if you want to order n different things, the number of ways of ordering n different things is just n factorial. Let’s check that. Here I have three things. So, what’s three factorial? Three factorial, number is 3 x 2 x 1 and that equals 6 and we have 6 things. So, that’s great.
So, that’s one way of counting. If you just want to know all the different ways of rearranging something or some collection of things, it’s just that number of things factorial. But, what if you wanted to look at something even a little bit more trickier? For example, suppose that we had a horse race. And we want to know all the different ways we could have first and second. Well, I don’t have horses here, but I do have fish. So, suppose that I have a fish race. I have a fish race and they can finish this race in any kind of order. They can finish in all sorts of possible orders. Now, I could figure out how many ways there are of ordering these things. Actually, how many ways are there? There are going to be four factorial. So, there’s going to be 4 x 3 x 2 x 1, which is actually 24. So there’s actually 24 different configurations.
But suppose all I care about is all the different ways of actually having a first and second place. Suppose all I care about who’s first and whose second in that order. Then how many different ways are there for me to arrange two things from a set of four in a particular order? I want to see all the different ways of having a first and second winner in the fish race. So, for example, this could be first and that could be second or this could be first and that could be second. Or this could be first and this could second or this could be first and this could be second. Or this could be first and this could be second or that could first and this could be second. There are a lot of them.
So, how could I actually figure that out? Well, this is actually the notion of a permutation. A permutation is just an arrangement of distinct objects in a definite order. So, here’s how you would actually figure that out. So, first of all the notation is, suppose that I have n things and I want to know how many different ways there are of me to take r of them and put them in a certain order. Then I would write that as the permutation of (n,r). That means that I have n things, in this case four, and I want to see how many different ways there are to take, in this case two of them, so r would be two, and order them first and second.
This is a race. I have first and second. I want to make a distinction between that. Well, the actual answer is--if you think about it this makes a little bit of sense, but you’ve got to think about it a lot. I’ll tell you anyway. First of all, how many ways are there just to order all four of these things? We already saw that’s just n factorial. But think about it. All I care about is who’s first and second. I don’t care about who’s third and fourth and the order of that. So, I should get rid of all the difference in the ways that the last people will finish. So, I’ll divide this by n – r, all factorial.
Since I only care about the first r place and the rest, which is n - r, I don’t care about. So, let me divide through by those. In fact, this will tell me how many different first and second place winners I could have in general. So, for this particular fishy example I would compute the permutation P and I have four and I want to know how many ways are there of having first and second places. So, I plug this in and I see 4 factorial divided by 4 - 2 factorial. What does that equal? That equals 4 factorial divided by 2 factorial. What is that? Well, you can write that out. That’s just 4 x 3 x 2 x 1 all divided by 2 x 1. So, I get some cancellation and I just see 12.
So, there are 12 different ways I can have a first and second place winner. This and this is one way, but this and this is a different way. So, that’s two. Then I could have three and four and then I could have five and six. Then I could have, and you can keep doing this forever, not forever, but you see that there are 12 different ways of having a first and second place winner. So, that actually shows you how to count how many different ways I can take a sub-collection of a certain group and order them in a certain way.
That’s permutation. Now, on your calculator, by the way, if you have a calculator that actually has the permutation key, the calculator may look like this, nPr. Like National Public Radio. That is the same thing as this and the formula is n factorial over n - r factorial. What does that do? It tells you the number of ways of arranging r things taken from a collection of n. That’s it. We’ll take a look at some applications of this up next.