Enter your Sign on user name and password.

• Follow us on:
Start learning today, and be successful in your academic & professional career. Start Today!
This is a quick preview of the lesson. For full access, please Log In or Sign up.
For more information, please see full course syllabus of Math Analysis

• ## Related Books

 1 answerLast reply by: Professor Selhorst-JonesThu Feb 12, 2015 1:42 AMPost by Jamal Tischler on February 10, 2015At the distinguishable permutations if we had the word ABBBC. There are six posibilities how we can arrange ABBBC. There are six pissibilities of how we can arrange BBBAC and so on. Is this why we divide it by 3! ?

### Permutations & Combinations

• A permutation is a way to order some set of objects. A combination is a way to choose some group of objects from a larger set of objects. In this case, we don't care about order, just which objects are selected.
• Multiplying successive positive integers is shown by factorial notation. The symbol `!' is the symbol for factorial, and it works like this (where n ∈ ℕ):
 n! = (n)(n−1)(n−2)…(3)(2)(1).
That is, it multiplies the number by every positive integer below the number. [We say `n!' as "n factorial".] To make certain math formulas easier to work with in the future, we define 0! = 1.
• The number of permutations of n objects (in other words, how many different orders the objects can be put in) is equal to
 n! = (n)(n−1)(n−2)…(3)(2)(1).
• The number of ways to order r objects out of a set of n objects total is
 n! (n−r)! .
This comes up often enough to have its own symbols: nPr    or    P(n,r).
• If we're permuting a set where some of the objects are not distinguishable from one another (like the letters of a word), the number of distinguishable permutations is
 n! (n1!)(n2!)…(nk!) ,
where n is the total number of objects in the set and n1, …, nk, are the numbers of each object "type".
• Given some set of n objects that we are going to choose r from (with no consideration for order), the number of possible combinations is
 n! r! ·(n−r)! .
This comes up often enough to have its own symbols: nCr,     (n || r),     C(n,r).

### Permutations & Combinations

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

• Intro 0:00
• Introduction 0:08
• Permutation
• Combination
• Towards a Permutation Formula 2:38
• How Many Ways Can We Arrange the Letters A, B, C, D, and E?
• Towards a Permutation Formula, cont.
• Factorial Notation 6:56
• Symbol Is '!'
• Examples
• Permutation of n Objects 8:44
• Permutation of r Objects out of n 9:04
• What If We Have More Objects Than We Have Slots to Fit Them Into?
• Permutation of r Objects Out of n, cont.
• Distinguishable Permutations 14:46
• What If Not All Of the Objects We're Permuting Are Distinguishable From Each Other?
• Distinguishable Permutations, cont.
• Combinations 19:04
• Combinations, cont.
• Example 1 23:10
• Example 2 26:16
• Example 3 28:28
• Example 4 31:52
• Example 5 33:58
• Example 6 36:34

### Transcription: Permutations & Combinations

Hi--welcome back to Educator.com.0000

Today, we are going to talk about permutations and combinations.0002

Consider if we had 5 distinct objects, like the letters a, b, c, d, and e.0006

We might want to know how many different orders we could put the objects in.0012

We call an ordering of objects a permutation: for example, one permutation would be abcde.0015

Another one would be if we put the letters in some different order, like bacde, or maybe aecdb.0023

We can see that there are going to be lots of different ways that we can order this out.0034

Each one of these is a permutation of the letters abcde, because it is an ordering of those objects.0037

So, one of the things we will be working on is how we can figure out how many permutations a set of objects has.0044

That is one of the major things we will be learning in this lesson.0049

The other thing we will be working on is: consider if we had that same group, abcde;0052

but this time, we are just going to pull three objects out of the larger group, but we don't care about order.0057

So, we are taking three out; we are choosing three objects, but this time the order of the selection doesn't matter, just which objects are selected.0062

We call a selection of objects a combination; for example, if we are talking about abcde again, we could pull out abc.0070

Notice: that is equivalent to pulling out bca, which is equivalent to pulling out cab, which is equivalent to pulling cba,0079

which is equivalent...and there are going to be another two, as well.0089

So, it doesn't matter what order we pull them out in; all that matters is what things we have at the end.0091

We don't care if we pull out cards from a deck in the order of...we don't normally care what order things come out in0096

when we are talking about a selection of objects--just that they are all there.0103

But a different would be if we had pulled out different letters, like, for example, abd, or if we had pulled out...0107

let me use yet another different color...bde; that would be yet another different selection.0115

Each one of these is a combination, a way of choosing letters from our group of letters.0125

In this lesson, we are going to figure out formulas for permutations and combinations for any number of objects.0132

These are important ideas, and they show up in a lot of different places in math, as well as a variety of other fields.0137

Being able to talk about the permutations of objects or the combinations of objects...0142

these are how we can choose things out; these are our really important ideas, and they show up in a lot of places.0146

It can be even kind of surprising how many places they will show up in.0151

So, this is definitely important stuff here.0153

All right, first we want to work on getting a permutation formula out of this.0156

How many ways can we arrange the letters a, b, c, d, and e? How many permutations of those letters are there?0159

Well, whatever way we order them, we know that they are going to take up a total of 5 slots.0166

We have 5 letters, so we are going to have to place them one after another; so there are going to have to be a total of 5 spaces taken up by these letters.0170

We will visualize this with empty boxes that are waiting to be filled.0177

Now, consider that very first slot: one of the letters has to go there, and we have a, b, c, d, and e.0181

So, since we have 5 letters, there are 5 choices to fill that first slot.0188

If we just look at the first slot, without even worrying about the other ones, we know0192

that if we fill the first slot first, we have, to begin with, 5 choices, because we could choose a, b, c, d, or e.0195

So, with that in mind, we say that there are 5 choices for our first slot.0203

Now, what if we are going to consider the second slot--how many choices do we have to fill that slot?0208

Well, we used to have 5 objects; we used to have a, b, c, d, and e.0213

But we used one of them in this first slot--we used one object on the first slot, so now we only have four objects for the second one.0218

Thus, there are four choices; now, notice: by this logic, we never actually mention which object was picked--just that we used some object.0227

We don't have to care what object is picked; let's really go ahead and make this clear.0234

Consider if we had a, b, c, d, and e; if we had chosen a to go into that first one, well, then, we would have b, c, d, and e for this box here.0238

So, we would have four possibilities for that box.0249

But what if we had chosen a different letter to go into the first box?0252

If instead we had chosen letter d to go into it, well, once again, we are still going to have 1, 2, 3, 4 choices: a, b, c, e.0256

So, we are going to have the same number of choices to go into that slot.0264

So, it doesn't matter which choice went into the first slot; we are going to end up having0269

four choices for the second slot, no matter what we chose in the first one.0273

So, we can say that there are four choices for the second slot.0277

This logic is going to work for each of the slots: for every slot we go down, there will be one less choice.0280

This is going to be consecutively true: there will be 5 for the first slot; and then, because we just used one of them,0287

there will be 4 for the second slot; and then, because we just used one of them in the second slot,0292

there will be 3 for the third slot, 2 for the fourth slot, and 1 for the fifth and final slot.0296

So, we use up one of them on each slot we work through.0302

Now, note that at this point, we now know how many choices are possible for each of the slots.0305

So, we can figure out the total possible permutations.0312

In our first slot, we have 5 choices; in the next one, we have 4 choices; 3 choices; 2 choices; 1 choice.0314

Well, we can think of each of these choices that we make as an event, and so our first event has 5 things,0320

and then the next event has 4 possibilities, and then the next event has 3 possibilities.0325

The next event has two possibilities, then one possibility.0328

We multiply them all together: 5 times 4 times 3 times 2 times 1; we get 120.0330

So, we are multiplying each of the ones for each of these slots.0336

Now, this logic will expand to any number of objects; so for any number n of distinct objects,0338

we can start with these n slots; so we will have n choices for the first slot, because we have n different objects to choose from.0345

Then, for the next one, we will have n - 1 (for the next slot), because we just used one for the first slot.0352

So, there is now one less for the second slot.0358

Then, for the following slot, there will be n - 2, because we just used one on the previous slot, so we are dropped down one again.0360

And this method will continue forever, until we finally get down to the nth slot here,0366

which will only have one remaining choice, because we have used everything else up by the time we get there.0370

To figure out the total number of possible permutations, we just multiply them all together.0377

We have a first choice at n, and a next choice at n - 1, the next choice at n - 2...0380

So, to figure out everything, we just multiply them all together; and that will tell us all of the possibilities that could come out of this.0385

The first one was n; the next one is n - 1; the next one is times n - 2; next, times n - 3; times n - 4...0390

We eventually get down to times 3 times 2 times 1.0399

Now, that is rather a lot to write out; so luckily, this comes up often enough0402

that we won't actually have to write out this whole long thing every time we want to talk about it.0409

It has its own special notation; that special notation is factorial notation.0413

Multiplying successive positive integers is shown by factorial notation.0418

The symbol that is just like an exclamation mark is the symbol for factorial, and it works like this:0422

where n is just contained in the natural numbers, any natural number n, n factorial is equal to n,0428

times n - 1, times n - 2, times n - 3...until we finally get down to 1.0434

That is, it is multiplying the number that we start with by every positive integer below that number.0441

We say this here as "n factorial"; for example, if we have 4!, then that is going to be 4, times...0447

what number is below that? 3, times...what number is below that? 2, times...what number is below that? 1.0456

There is nowhere farther to go down; so we have 4 times 3 times 2 times 1.0461

The same thing happens if we have 27!: 27 times 26 times 25 times 24 times 23 times...we finally work our way down to 1.0466

Now, one special thing here: to make certain math formulas easier to work with in the future,0476

we just define 0! equal to 1; it makes things a lot easier if we say that 0! is equal to 1,0482

even though it doesn't quite make sense with this definition that we just defined here.0489

It is not quite as natural a thing to say; but it will make things work out a lot more smoothly in the future.0492

So, just trust me on this; it makes sense to say 0! = 1; it will keep things running more smoothly in the future.0498

So, we just make that definition; everything else, though, works like we would expect.0503

1! is just 1 times itself, so 1; 2! is 2 times 1; 3! is 3 times 2 times 1, and going out forever.0507

But 0! has this special thing, where we just say that it is equal to 1; we just have to remember that.0514

All right, going back to permutation of objects: with this notation, factorial notation, learned,0519

we can now easily and succinctly write out the formula for permutation.0523

The number of permutations of n objects, where they are all distinct objects0527

(in other words, how many different orders we can put the objects into) is equal to n!--it is as simple as that.0531

The permutation of r objects out of n: what if we have more objects than we have slots to fit them into?0539

For example, say we had a bag containing one of each letter on a tile.0546

There are 26 letters in the alphabet we are using, so we have 26 tiles in this bag.0550

And on each one of the tiles is a different letter; so there is an a in there, a b in there, a c in there, a d in there...all the way down to z.0554

So, if we pull out one tile at a time, and we place it down in the order that it is pulled,0562

and we do this five times, how many words are possible?0566

"Words," of course (that should say "how" with a capital H)...by "word," I just mean "string of letters."0570

Most of these aren't going to actually have any real meaning.0577

So, we are just saying, "How many different things can we make out of this?"0580

We would do this with the exact same logic that we did previously: how many choices do we have for the first one?0584

Well, we have 26 choices for the first one, because we are pulling from a bag of 26 letters.0589

For the next one, there are 25 for the next one, because we just used one of the letters already;0595

so that has reduced our number of choices, so we have 25 letters.0600

We have 24 for the one following that (we have used one); we have 23 for the one following that (we have used one).0603

We have 22 for that one; that means we have now put down 5 letters.0608

So, the total possible number of words that will come out of these 5 letters is 26 choices for the first one, 25...0612

We multiply them all together: 26 times 25 times 24 times 23 times 22...we have figured it out.0618

The logic that we just used for that previous idea, that previous example, would work for any similar problem.0625

So, if you find that easy, and that makes a lot of sense to you, go ahead and use that.0631

But we are going to obtain our general formula by looking at things a little bit differently.0634

So, start by considering ordering 26 objects: this many objects here...I didn't want to put down 26 squares;0638

it is 26 squares that we are pretending are there.0645

Now, from before, we know that there are 26! possible orderings.0647

If we have 26 different squares, then there are 26 factorial ways to order those squares; that is what we just figured out with permutations.0652

However, that is not exactly what we are looking for, for that previous problem.0660

We only care about the position of the first five letters.0665

The following 21 letters--we don't care about that; we don't care about the last 21 letters, these letters over here,0670

because they don't affect the thing that we are looking at.0680

They just stay in the bag, those last 21 letters; we are only concerned with what the first 5 things to come out are.0682

So, when we calculated the 26! permutations for 26 letters, we were counting the order of the last 21, as well.0688

We were counting this part here, the tail of the thing.0695

But now we need to get rid of that; we don't care about the order of that.0699

We can think of this as...we put down the letters; we put down our first, second, third, fourth, and fifth letter.0703

And then, we decide, "I'll put down the rest of the 21, as well."0708

But the ones that are past the edge of those first 5--they just get shoved back into the bag.0711

Only the first five end up counting; so we don't actually end up caring what this latter 21's order was.0717

How do we get rid of that order? We do it by dividing out all the ways that we could order,0723

all of the possible orderings for those last 21 letters.0727

How many ways can we order 21 letters? We can order them 21! ways.0731

So, we have 26! possible total; but then, we are dividing out the stuff that we don't care about, that 21! for the tail, this last 21 letters.0735

So, 26! for the whole thing, divided by 21! for the bottom: we could rewrite that as 26 times 25 times 24 times 23 times 22 times 21 times 20 times 19...0745

But since we are going to go on forever, we could just say "times 21!"--0759

26, 25, 24, 23, 22, 21!--because that just says to keep going down to 1, as well.0763

So, that will be the same thing as 26!.0769

Well, we have 21! on the bottom, as well, so we can cancel them out now, which allows us to get 26 times 25 times 24 times 23 times 22,0772

which is the exact same thing as we had previously; so it seems like this is a reasonable way to think about this.0781

This actually makes sense; we can now extend this logic to a general point, where we can use this logic0786

to figure out any general formula for a permutation of r objects, pulled from a set of n objects total.0791

Previously, we were pulling 5 objects, r = 5, from a set of 26 objects, the permutation of 5 objects from a set of 26 objects.0798

Now, all of the objects total would have n!, if we were doing this in general: n objects, n! permutations total possible.0809

All objects together are n! permutations.0817

But we don't care about all of the objects; we only care about the first r objects.0821

We need to get rid of that stuff that we don't care about.0826

We don't care about the later n - r objects, so we get rid of the ways that we can order that tail, that back n - r,0829

because we only care about the first r, so the rest of them will be n - r.0836

So, we do this by dividing by (n - r)!.0840

Previously, that was 26 - 5, so 21, factorial; that gets us n! divided by the part that we don't care about, (n - r)!.0843

This idea comes up often enough that it has its own symbols: a little n in front of a big P, and then a little r, or p of n, comma, r,0855

where the n is how many objects we have total, and r is how many permutations--the number of objects we are using for our permutations.0862

nPr or p(n,r): both are fine ways to show this.0871

And you also don't have to use these methods; you can also just talk about it and explain it and go through with this formula.0875

But if we talk about it a lot, we might end up using these symbols.0881

What about distinguishable permutations? So far, everything we have looked at--0884

we have had cases where all of the objects we are rearranging are all completely distinct from one another.0888

For example, when we were talking about the bag full of letter tiles, we only had one of each letter.0892

So, we could tell the difference between each of the tiles in there.0897

But what if they aren't going to be distinct from each other?0900

For example, let's consider a nice, simple example: if we are going to permute the word "bob."0903

If the b's are distinct (that way, we have some way of telling one b from the other one--0909

say one of them is in a color red and the other one is just in the color black),0913

then we can tell the difference between one b and the other b, so we have three distinct objects,0917

which means 3!, or 6, possible permutations.0921

You can see all of the permutations here: we have all of the different ways of rearranging it.0926

But if we take away this color, if the b's are not distinct, this number will shrink down.0930

So, notice that where we used to have b's, it mattered if the red b or the black b came first.0937

It mattered which one was the first one for those b's.0943

But if we swap their locations, whether it's swapping around o, or they are next to each other,0946

we are not going to be able to tell the difference between swapping their locations.0950

Now, all of the times the b's were in the same location, they cancel out; they disappear; we are only left with one of them.0953

For example, over here we have bob; so over here, this bob is now no longer distinguishable from it.0959

bbo is now no longer distinguishable from the other bbo; and obb is no longer distinguishable from this obb.0964

So, we are left with only three different ways of doing it.0972

The order that the b's appear in no longer matters.0976

If we are going to figure it out from the number of permutations, we have to cancel it out.0979

We started with 3! equal to 6 possible permutations of the letters b-o-b.0983

But since we can't tell the difference between one b and the other b, it doesn't matter which order we put them down in.0989

So, we have to divide all of the ways we can order our b's.0995

How many ways can we order our b's? There are 2 b's, so it is 2!, which is just equal to 2.0998

So, we divide 3!, the total thing being arranged, divided by the ways that we can arrange the thing that is identical, 2!.1003

So, 3!/2! = 6/2, which equals 3, which is the exact same thing that we got here when we actually worked it out by hand and saw each of the words.1011

This logic will work in general; if we have a set of objects where some are not distinct from others,1022

we take the total permutations possible if they were all distinct,1027

then divide by how many ways the non-distinct objects can be ordered.1031

So, we divide by ways non-distinct objects can be ordered.1035

This can be done multiple times.1041

Let there be a set of n objects; we have n objects, and there are various types of object in the set.1043

In a single type, if you are in a type, the objects are not distinct from each other.1051

So, for example, in the previous one, we had type b and type o in our previous example.1058

Well, if you are a type b letter, there is no way to tell you from the other type b letter.1062

If you are a type o letter, there is no way to tell you from the other o letter; but there is just the one of them.1066

So, we had type b's and type o.1071

We can expand this to a general thing of n1 being the number of the objects of the first type;1073

n2 will be the number of the objects of the second type, and 3 the third type,1078

and so on until we get to however many types we have--let's say k types.1082

Then, in general, n1 + n2 +...up until our nk,1086

the number of each type, added together, is equal to the total number of objects.1092

This makes sense; we had 2 b's and one o; 2 + 1 equals 3, which is the total number of letters that we had in the word bob.1100

The number of distinguishable permutations is the number of ways that we can order our n objects, n!,1108

divided by the number of ways we can order type 1 objects, the number of ways we can order type 2 objects...1116

up until we get the number of ways we can order type k objects.1121

So, n! is divided by (n1!)(n2!)...up until (nk!).1125

The way we can order the whole thing is divided by the way we can order each of the subtypes.1131

Finally, combinations: let's reconsider the bag containing one of each letter, 26 in total.1138

We will still pull out five letters, but this time we don't care about the order of those five letters.1144

It doesn't matter if it goes in the way we already pulled it out, or we can swap the orders;1148

and it just is all the same thing from our point of view; order does not matter in there.1153

Now, from our previous work, we know that there are 26!/21! possibilities for those first five slots, if we care about order.1157

That is what we figured out with nPr: 26 is n; r = 5, because we are choosing from 26 objects; we are pulling out 5; and we care about order.1166

So, P gets us 26! divided by (26 - 5)!, or 21!.1176

So, that gets us how many ways we can have 5 letters at the front, if we care about order.1183

But we don't care about order; we no longer care about the order of those first five letters.1188

How can we get rid of it--how can we end up letting these things move around and having it be the same from our point of view?1194

We divide out the number of ways we can order those first five letters.1200

The number of ways we can order 5 things is 5!, so we divide what we have for the number of ways1205

that we can pull out these first five letters, with order...we divide that by 5!.1212

The number of ways we can have those first five letters, with orders, is 26!/21!.1216

And then, we just figured out that the number of ways we can order these first five letters is 5!.1223

So, we divide by a further 5!; so it is 26!/5!, times 21!.1229

These are all of the ways to choose five letters from the bag.1235

"Choose" is a special word that means that we are doing this combination thing1240

where we don't care about the order of the objects; we just care about what came out of the bag,1243

but not the order that they came out of the bag in; the special word is "choose."1247

This logic can be generalized: let there be a set of n objects that we want to choose from.1252

We have n objects that we are pulling from, and we want to choose r objects out of it, but we do not care about order.1257

Order is not important to us; we are pulling out r objects from a set of n objects, but we don't care about the order that they come out in.1265

So, there are nPr, n!/(n - r)! ways to choose r with order.1273

nPr gives us the ways to choose r, if we care about the order of those r objects.1283

But we don't care about the order of those r objects; we don't care about order.1288

So, since we don't care about order, we have to get rid of how many ways we can order those r objects.1293

We can do that by dividing by r!, because r! tells us all of the ways that we can order r objects.1298

So, we divide by r! to get rid of the order on those first r objects.1304

If there is a set of n objects...let there be a set of n objects; if you choose r of them,1310

with no regard for the order of choice (it doesn't matter which comes first out of the bag),1319

the number of possible ways to do this--the number of combinations we have--1323

is n! divided by the number of ways that we can order the choices that we are pulling out, r!,1327

times (n - r)!, the number of ways that we can order the things that we are not pulling out: n!/r! times (n - r)!.1334

And notice that there is this nice thing of r + (n - r) comes out to be n; so these two numbers here total up to n, what we started with.1342

This idea comes up often enough that it has its own symbols.1359

It comes up even more than the permutations thing that we talked about previously.1361

We have nCr, nr like this, where we have this large parentheses on the sides, and n is above r; or c of n, comma, r.1365

In any of these cases, we say any of these aloud as "n choose r."1378

We have a set of n objects, and we are choosing r out of them; and choosing means that we don't care about the order that we pull out.1382

All right, we are ready for our examples here.1390

The first example: How many ways are there to order a standard deck of 52 playing cards?1391

Then, compare that number to the number of atoms that make up the earth.1397

How many ways are there to order a standard of 52 cards?1401

Well, we can do this by starting with a visual understanding of it.1403

We have 52 slots that we are going to end up putting down, because we are going to place down each of these cards.1406

There are a bunch of different slots here; we work our way through all of them.1412

Well, for our first one, we have placed down the first card; there are 52 choices for our first card.1416

Then, for the next card, we used up one of the choices, so there are 51 choices for the following card.1422

Then, we put down our next card; there are 50 choices for that one, because we have used up 2 so far.1427

We work our way down until, finally, we get down to 2; we get down to 1.1432

How do we talk about this? Well, the number of total possibilities is going to be 52 times 51 times 50 times...until we finally get down to the 1.1436

52 times 51 times 50 times...times 2 times 1: luckily, there is that nice, convenient notation,1444

so that we don't have to actually write this whole thing out.1455

We just have 52!: that is the number of ways to order a 52-card deck of playing cards: 52! number of ways.1457

And of course, we might not have a very good sense of how big 52! is.1467

We are not used to working with factorials that much; it gets kind of hard to know for larger numbers.1471

So, let's work it out...of course, working it out by hand is going to be awful, so we use a calculator.1474

We get a calculator to do this, and we are probably not even going to want to say 52 times 51 times 50 times 49...1479

That is going to take us forever; luckily, most calculators have a factorial button on them,1484

or some way to go through a menu so that you can get that exclamation mark symbol and use that.1488

If you work that out, you put 52, and then that exclamation mark symbol.1493

You put it into your calculator, and that comes out to be approximately 8x1067 ways to order your deck.1497

Now, notice: the earth is made up of approximately 1050 atoms, whereas all of the ways1510

that we can order a deck of 52 cards is 8x1067 ways: that is a massive amount more.1518

If we were to divide the number of ways that you can order that deck by the size of the earth in atoms,1525

that would leave us with around 8x1017 ways, which means that the number of atoms in Earth1532

is one-millionth, one-millionth, one-MILLIONTH--one-millionth of one-millionth of one-millionth1539

of the number of ways that you can order a deck of cards, approximately.1545

That is crazy--that is an insane amount of quantities.1549

With this fairly small, simple thing, we wouldn't think that you could get that many possibilities out of it.1554

These numbers get huge really, really quickly; it is really, really interesting to think about that.1559

You also might end up seeing, if you put a larger number, like, say, 100!, into your calculator,1563

it will say "overflow," because the number is so big that the calculator can't even work with it anymore.1567

The second example: If 20 people run in a race, how many possible ways are there for runners to come in first, second, and third?1573

We can do this, once again, by visualizing this with boxes.1579

Our first box is the first-place box; and then, our second box is the second-place box; and then, our third box is the third-place box.1582

And we don't care about the fourth, fifth, or sixth; we don't care about further boxes, because all we were asked for is ways for first, second, and third.1592

So, how many choices are there for the first box?1598

Well, we were told that there are 20 people running in the race, so there are 20 choices for the first box.1601

For the second box, well, we just used one of those, so there are now 19.1605

For the third box, we just used another, so they are now 18, which is going to mean 20 times 19 times 18 different ways.1608

Alternatively, we could have looked at this as nPr: how can we choose r objects out of a group of n objects, if we care about the order?--1617

because we care about the order; there is a big difference between first and second.1626

So, we care about that; our n, in this case, is 20 people, 20p, and then our r is 3 people, because we are looking at pulling out 3 people, caring about order.1629

That gives us 20!, divided by (20 - 3)!; we keep working with this; that is the same thing as 20! over...20 - 3 is 17, factorial.1640

We can rewrite 20! as 20 times 19 times 18 times 17 times 16 times 15...1656

well, 17 all the way down to 1...we can also just write that as 17!; and now we have the same thing on the top and the bottom.1663

So, 7! is on the top; 7! is on the bottom; they cancel out, and we are left with 20 times 19 times 18.1670

So, either way we work this out, whether we work this out visually with the boxes,1677

and seeing how many choices there are; or we work it out with that formula we figured out earlier,1681

for a general formula, we are going to get the same thing, which is good.1685

20 times 19 times 18 is 6,840 different ways for the race to end.1689

We can have 6,840 different possibilities for the runners to come in first, second, and third, if we have 20 people running in the race.1697

Example 3: How many ways are there to arrange the letters of "senseless" into a distinguishable word?1704

Now, that is to say...the word doesn't have to make sense; it just needs to be a single string of letters,1710

and be distinct from the other words--different from another way of putting it.1714

But most of these words, if not pretty much all of them, are not going to make sense.1717

Let's work through this: how many letter types do we have?1721

This is types of objects; this is distinguishable permutations, which we remember from before:1724

it is n! divided by the number of our first type, factorial, times the number of our second type,1728

factorial, up until our last type, times each other, factorial.1732

So, how many s's do we have? The number of s's that we have is 1, 2, 3, 4 s's total.1735

The number of e's that we have is 1e, 2e, 3 e's total.1743

The number of n's that we have is 1 n; that is all of our n's, 1.1750

And the number of l's that we have is 1 l, as well.1755

How many does that mean total? Our total letters are 4 + 3 + 1 + 1, so 7, 8, 9, which we would also get if we counted 1, 2, 3, 4, 5, 6, 7, 8, 9.1760

So good: things make sense so far.1774

The total ways that we can arrange all of these letters is 9!.1776

But then, we divide it by each of the ways that we can order the types of letter,1782

because we don't care about the order the s's come in--they are all the same to us.1787

So, it doesn't matter which s comes first; we have 4 s's, so 4! times...we have 3 e's, so 3!, times...1 n, so 1!, times...1 l, so 1!.1790

So, 9! is divided by 4! times 3! times 1! times 1!.1806

Now, 1! and 1!...well, 1! is just 1; that is it; there is no further down to go, so 1! is just 1.1811

1 times 1...we can just get rid of them for now.1819

At this point, we have 9! over 4! times 3!.1821

We could punch that into a calculator if we wanted, and it would give us the answer.1828

But we also might want to simplify things a little bit: 9! we can break down into 9 times 8 times 7 times 6 times 5 times 4!,1831

divided by 4! times 3!; well, we have a 4! here on the bottom, and a 4! on top; so they cancel out.1841

We have 9 times 8 times 7 times 6 times 5 on top at this point.1849

3! is 3 times 2 times 1; 3 times 2 times 1 is 6, so we have a 6 on the bottom now.1856

We have a 6 on top and a 6 on the bottom; they cancel out, so we are left with 9 times 8 times 7 times 5.1862

We plug that into a calculator; we work it out, and we get 2,520 different ways that we can order the letters of "senseless"1870

and still make a distinguishable word that is different from all of the other ones.1879

That is very different than just all of the ways we can order 9 things,1883

because, in this case, some of the things look the exact same as others, so we can't tell the difference.1886

For example, if we swap this s with this s here, we can't tell the difference; any s is just the same to us.1890

So, we can't tell the difference; so we have to be able to divide by the number of ways we can move around our s's.1897

And since we had a total of 4 s's, we have to divide 4!; that is the logic going on here.1902

And we get our answer: 2,520.1907

The fourth example: Given a standard deck of 52 playing cards, how many ways are there to choose 5 cards from the deck?1910

Notice: it said "choose," and "choose" means that order does not matter.1916

So, how does choose work? If it is 52, choose 5 things out (alternatively, we could write it this way,1921

with the large parentheses, and the 52 choose 5, where the number that we are pulling out of1929

is above the number of things we are pulling out), well, we are choosing 5 cards.1933

How many ways are there to pull out 5 cards, if we don't care about the order, from 52?1939

Choose works this way: the number of things, 52!, divided by the number of things that we are pulling out,1944

times 52...the whole number of things, minus the number of things we are pulling out, factorial.1951

That gets us 52! over 5!, times 47!, because 52 - 5 is 47.1958

We can rewrite 52! as 52 times 51 times 50 times 49 times 48 times 47!.1968

So now, we have a 47! on the bottom and on the top; 5!, 47! here; cancel; cancel...1981

So, we have 52 times 51 times 50 times 49 times 48, divided by 5!.1989

5! comes out to be 120; but it doesn't matter.1998

We can plug all of this into a calculator, one way or the other.2002

We work it out in our calculator, and we get 2 million, 598 thousand, 960 different ways that we can pull out 5 cards from the deck.2004

And that is not including order, so that means 2 million, 598 thousand, 960 5-card hands that are distinct from each other.2016

That is a whole lot of possibilities in something that seems very small to begin with, where it managed to get these very large numbers of possibilities.2023

Possibility grows at an incredibly fast rate.2030

The fifth example: How many 2-person relationships are possible within a class of 30 people?2033

The first thing to think about is what it means to have a 2-person relationship.2038

What does a 2-person relationship in a group of people mean?2042

Well, let's think about this: if we have some person here...we have blue man; we have red man; we have green man;2045

what does a relationship between any of these people look like?2057

Well, a relationship is red man and blue man talking to each other, or blue man and green man2059

talking to each other, or green man and red man talking to each other.2064

That is a 2-person relationship--how these connections are, like this.2066

So, what we are looking at is how it is possible to pull out these two people, linked together,2071

or these two people, linked together, or these two people, linked together.2077

So, in another way, it is a way of asking how many ways it is possible to pull out two people from the group,2081

because we pull them out, and that is a relationship; we pull out a different two people, and that is a relationship.2087

You pull out some person and some other person; that is a relationship between them--that is a 2-person relationship.2091

Even if they don't know each other, that is just their relationship: not knowing each other.2097

If we have a group of 30 people, then that, from a group of 30 people, means that we are pulling out 2 people at a time.2101

A 2-person relationship is pulling out 2 people and putting them next to each other.2109

30 choose 2 is 30!, the total number factorial, divided by the number that we are pulling out, factorial,2112

times the number that we have total, minus the number we are pulling out, factorial...2121

so 30! over 2!, times (30 - 2)!; keep working on that...we have 30!/2!, times 28!.2125

We can rewrite the top as 30 times 29 times 28!, divided by 2! times 28!.2134

28! is on the top and the bottom; they cancel each other out.2144

2! is just 2 times 1, so that is just 2; so on the top, we still have 30 times 29, and on the bottom, we have 2 times 1, or 2.2148

And 30/2 is 15, so we have 15 times 29; 15 times 29 comes out to 435 different possible relationships between the people in this class,2158

which is, once again, a fairly large number for not that many people.2173

Only 30 people in a classroom give us 435 different 2-person connections between those:2176

435 different possible relationships that you can examine, which is a really large number that grows out very quickly.2182

The final example, Example 6: A group of 50 students are going to be assigned to playing 4 different sports.2189

There are 8 open slots in badminton, 13 in football, 17 in baseball, and 12 in volleyball.2195

Notice that that makes a total of 50 slots.2201

How many ways can the students be assigned?2203

We are going to look at this in two different ways.2205

The first way that we are going to look at it is through the idea of choice.2207

We are going to make different choices to begin with.2210

We start, and let's work on badminton first: we have 8 open slots for badminton.2214

What we are looking at is how many ways there are to choose 8 players for the badminton group.2219

We have 50 students that we are choosing from; how can we choose...50 choose 8 is all the ways we can choose our badminton group.2225

Next, let's work on the football group.2233

Football is not going to be 50 choose 13, because how many people do we have at this point?2236

Well, we just did badminton; we are now reduced by the 8 students we put into the badminton team.2243

So, we don't have them to work with anymore; so it is 50 - 8 students; that is how many people are left.2249

50 - 8 is 42; so there are now 42 students left, if we are looking for how we are going to put football positions around.2254

42 choose 13 is how many we can have for football at this point.2262

That is all the choices for football after we have already done the choices for badminton.2266

Next, let's look at how many we can put into baseball.2270

Once again, we have to reduce the student pool that is left by how many people we have already put in for other things.2273

We already had 13 go into football from 42; so 42 - 13 becomes 29.2279

And now, we are choosing 17 for baseball, and finally, 12 for volleyball.2286

29 - 17 means we have 12 students left; and of course, every single one of them is automatically going to be chosen for volleyball.2290

12 students...choosing 12 students out of them...well, every one of them is going to have to go into volleyball, because they are the group left over.2297

If we work this out with what these mean mathematically, 50 choose 8 is 50! over 8! times (50 - 8), so 42, factorial.2303

Next, it is times 42!, divided by 13!, times (42 - 13)! (that comes out to be 29!).2314

The next one is times 29!, what we are choosing out of, divided by 17!, how many we are choosing out;2326

29 - 17 is 12, factorial; times 12!, divided by 12! times 0!; 12 - 12 gets us 0.2332

That is an important reason, right there: we see why we defined 0!...remember: 0! = 1.2343

We just defined that, and that is so we don't have things like dividing by 0 happen over here.2350

That 0! just cancels out nicely.2354

Now, notice: at this point, we have 42! on the bottom here and 42! up here; so they cancel each other.2356

The same thing: 29! and 29! cancel; 12! and 12! cancel.2362

That leaves us, in the end, 50! on the top, divided by 8!, times 13!, times the 17!, times the 12!.2367

That is the total number of ways that we could put this out for all of our team assignments.2388

Now, notice: that is an exact perfect answer; that is correct, but it is not a number, so we might want to use a calculator to get an approximate number.2394

So, we go into our calculator and find the factorial button (that exclamation mark) somewhere in our menus.2403

We will be able to figure it out and put it down that way, and we will be able to get the answer.2410

That is what it comes out to be; we will have to work through a calculator to get an approximate answer, but that is the precise answer.2413

This is the answer right here.2419

Now, alternatively, we could have done this in a totally different way.2421

We could have also done this through arrangement.2425

Now, the arrangement way is a little bit more complicated to think through, I think.2427

But it works faster, and I think it is a little more satisfying.2432

But the choice method works great; if it makes sense, and this arrangement one doesn't quite make sense, use the choice method.2436

Whatever makes the most sense to you is the way you want to work.2440

But the arrangement method--you might find that this makes sense, and it will go even faster.2443

The way we have to think about this, first, is: we can think about this as putting all 50 students in a line.2447

We line them up alphabetically (or whatever); we line up the 50 students, and then we keep them there.2452

We don't let them move; they just stay in their positions.2457

We have lined-up students there; next, we think of badminton, football, baseball, volleyball as cards.2459

There is a badminton card, and we have a total of 8 badminton cards.2467

And then...let's make that a bd, because it is kind of hard to tell the difference between badminton and baseball, if they both have that.2473

So, bd and bd are badminton cards.2479

And then, we have our football cards; how many football cards do we have? Well, we have 13 football cards.2483

How many baseball cards do we have? Well, we have 17 baseball cards.2490

And then, we have how many volleyball cards? We have 12 volleyball cards.2497

So, we can think of this as these cards; and now, the question is, "How can we hand these cards out to the students?"2506

If we think of our students as just standing there, little boxes, waiting to receive their cards...2511

There are a total of 50 things, and then the question is, "How can we place these cards in?"2517

Well, it is a question of how we can arrange these cards and hand them over to those boxes.2521

We arrange the cards in some line, and then we hand it over to the line of students waiting there.2526

So, how many ways are there to arrange this set of cards?2531

Well, we have a total of 50 cards; this comes out to 50 total, so we have 50!, divided by...2535

what are we going to divide by?--well, how many ways can we arrange the badminton cards?2543

It doesn't matter if you get the first badminton card or the second badminton card or the last badminton card.2547

They all mean the same thing, "Go onto the badminton team."2551

So, it doesn't matter which way we arrange our badmintons; so we divide by 8!, because the arrangement of our badminton cards doesn't matter.2554

Next, we divide by 13!, all of the ways that we can arrange our football cards.2564

Then, we divide by 17!, all of the ways that we can arrange our baseball cards.2568

And then finally, we divide by 12!, all of the ways that we can arrange our volleyball cards.2573

So, what we are seeing here is distinguishable permutations of our cards--2577

all of the ways that we can have distinguishable permutations of these 50 assignment cards.2581

We can look at it as choosing students for the teams, but we can also look at it as arranging cards2585

that we then hand over to the line of students who just wait there.2591

So, this also ends up getting us the answer; and notice that they are the exact same thing.2595

So, both ways are equivalent; they get us to the same thing, which is good; that is what we hoped for.2601

If we work this out with a calculator, we end up getting that it comes out to approximately2605

the ridiculously large 7.1x1026 ways that we can arrange, putting our students into these teams.2609

That is a ridiculously large number, considering that we are just putting 50 students into 4 teams.2619

It is amazing how fast these things get when we are working in combinatorics, when we are working with permutations and combinations--pretty cool.2623

All right, that finishes this lesson; in the next lesson, we will see how we can apply this stuff to probability,2630

and how we can use all of our work here to get an idea of how likely a given event is to happen.2635

All right, we will see you at Educator.com later--goodbye!2640