For more information, please see full course syllabus of Math Analysis

For more information, please see full course syllabus of Math Analysis

### 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 ∈ ℕ):

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.n! = (n)(n−1)(n−2)…(3)(2)(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

This comes up often enough to have its own symbols:n! (n−r)!

. _{n}P_{r}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

where n is the total number of objects in the set and nn! (n_{1}!)(n_{2}!)…(n_{k}!)

, _{1}, …, n_{k}, 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

This comes up often enough to have its own symbols:n! r! ·(n−r)!

. _{n}C_{r}, (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
- Introduction
- Towards a Permutation Formula
- Factorial Notation
- Permutation of n Objects
- Permutation of r Objects out of n
- What If We Have More Objects Than We Have Slots to Fit Them Into?
- Permutation of r Objects Out of n, cont.
- Distinguishable Permutations
- What If Not All Of the Objects We're Permuting Are Distinguishable From Each Other?
- Distinguishable Permutations, cont.
- Combinations
- Example 1
- Example 2
- Example 3
- Example 4
- Example 5
- Example 6

- 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

### Math Analysis Online

### 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 in*0096

*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 know*0192

*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 having*0269

*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 n ^{th} 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 enough*0402

*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 objects*0527

*(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 logic*0786

*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 n _{1} being the number of the objects of the first type;*1073

*n _{2} 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, n _{1} + n_{2} +...up until our n_{k},*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 (n _{1}!)(n_{2}!)...up until (n_{k}!).*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 ways*1205

*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 thing*1240

*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 8x10 ^{67} ways to order your deck.*1497

*Now, notice: the earth is made up of approximately 10 ^{50} atoms, whereas all of the ways*1510

*that we can order a deck of 52 cards is 8x10 ^{67} 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 8x10 ^{17} ways, which means that the number of atoms in Earth*1532

*is one-millionth, one- millionth, one-MILLIONTH--one-millionth of one-millionth of one-millionth*1539

*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 of*1929

*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 man*2059

*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 cards*2585

*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 approximately*2605

*the ridiculously large 7.1x10 ^{26} 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

1 answer

Last reply by: Professor Selhorst-Jones

Thu Feb 12, 2015 1:42 AM

Post by Jamal Tischler on February 10, 2015

At 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! ?