[MUSIC] Welcome back to class. In the last lecture we talked about enumerations. Those are pretty straight forward. They were just one, two, three, four. In this lecture, the primary topic are going to be permutations. That sounds kind of ominously mathematical. But it turns out the distinction between enumerations and permutations is not that tough to understand. When we enumerate things, we allow repeated outcomes. We're generating permutations, we don't allow repeated outcomes. There are a couple of consequences of this. For example, we're building a permutation, and kind of the maximum length of the permutation is limited by the number or items in the set, which we can't repeat. The other one is that we can kind of build new permutations by just shuffling the items in the existing permutation. In fact, that's really what it means to permute something. It just means to shuffle things around. So we'll go over some definitions, look at some formula, and do some examples, and maybe act a little goofy. So let's go and get into lecture. [SOUND] All right. Before we talk about permutations and combinations. I want to refresh your memory real quickly, about a mathematical function that we'll use to count the numbers of permutations and combinations associated with a set of outcomes. That function is the factorial function. You probably see it written mathematically as something of a form, some number with an exclamation point. For example we have M factorial here. And that's just simply the product of all of the numbers from one to M. So for example, for factorial is one times two times three times four, that's 24. To make the formulas we're going to use with permutations and combinations work out more elegantly. Zero factorial is usually defined to be one. We can compute factorials in Python using the math package. So let's go through and actually just give that a shot. So I'm going to import this into Code Sculptor and I'm going to fire off run and it looks like that six factorial is exactly 720. So that's one times two times three times four times five times six. Do a little math, it's exactly that. Let's just confirm that zero factorial is one. Okay. Looks pretty good. Okay. Let's talk about permutations. So a permutation of length N is really nothing more than a sequence of outcomes of length N where we don't allow any repeated outcomes. So for example, if our set of outcomes corresponded to maybe something from a lottery, you had the numbers one to 59, then the sequence 34, 12, 27, 56, 58 is a permutation. Every outcome in that sequence is distinct. But, this sequence, 23, 11, 23, 3, 47, is not a permutation because we repeated 23. So the difference between kind of what we were doing in the last lecture and here, is just we're now allowing repetitions in this case. So let's go ahead and look at some code that actually generates permutation. So we have jumped over into code sculptor, and I have a function gen permutation, I've hidden it. You have to actually build this in your homework; it's not to difficult. It's a very simple modification of gen sequences. And here I've got some examples we can actually run to build some permutations. So the first thing I'm going to do is I'm going to take my set of outcomes to be the number zero to nine, and I'm going to look at all permutations of length zero. So let's try to see how many permutations of length zero we have. And we're going to have one. It's going to be the empty sequence. Let's run that. Sure enough. There was one permutation and it was the empty sequence. Let's modify this and generate all permutations of length one. It's very simple. There are ten permutations and each of the sequences are the sequence of zero, the sequence of one, the sequence of two and so forth. So, looks like nothing's changed so far. Let's choose, look at a permutation of length two. So if I run that, notice that I get 90 permutations. Before when I was doing ,enumeration I had a hundred different sequences. So this looks kind of similar I have (0,1),( 0,2) dah, dah, dah, dah, dah. Now, wait a sec, I was missing something. Before I add (0,0),( 0,0) is not allowed.that class actually goes scroll forward here. So if you look this we see let's see. We see (1,0) and then we skip to (1,2). We didn't generate a permutation 1, 1 because things are being repeated. Let's go and do an example here with colors real quick. So, let's look at all the permutations of the three colors, red, green, blue. So if I run that, I get six permutations. And let's see, if you look at it, I have red green, red blue. Then I have green red, green blue, and then I finally have blue red and blue green. Let's look at all the ones of length three. [UNKNOWN] on that, I get six again. In fact, things didn't really change because the first two elements in the permutation kind of forced us to choose only one outcome for the last one because we kind of exhausted all the other outcomes. So, really here, when we had something of length 2 if we chose red and green the last element in the permutation had to be blue. We couldn't repeat an outcome. Okay. So once you've kind of done your homework, you might play around with this a little more if you want to get more experiences, what permutations look like. All right. Let's talk a little bit about counting the number of permutations. So in the last lecture we had a really simple formula for kind of counting the number of enumerations that were possible. If our set of outcomes had M items and we're looking at things of length N, it was M to the N. If our set of outcomes has M items and we're looking at permutations of length N, there's again, a fairly simple formula involving factorials that lets us compute that. And if we look over here, the analysis is pretty straight forward when we're generating the first element of permutation we have an outcomes to choose from. Now when we generate the second one, well one of them has been excluded, so really have M minus one possibilities. Then we generate the third is M minus two, all the way down to M minus M plus one possibilities for the, the last item in that sequence of link M. Now, you can write by using factorials very easily. You can write it as M factorial divided by M minus N factorial. Why does that work? Because there's a term of M minus N above the numerator and denominator, so that actually cancels out, so it cancels out anything would be M minus N right here. In fact, it cancels out everything that's smaller than M minus N. So let's go actually work in Python and compute, use this formula to compute the number of permutations for a lottery. All right. Let's use our formula for counting the number of permutations, and try to determine kind of how many kind of possible outcomes we can have from a lottery in which we have 59 balls, we draw six of them one at a time. So we don't put them back, so there's no repetition. And the order is important. I just see something here. Let me check. I think we're safe. I don't see Scott. I just noticed I didn't use a dock string, so pretend I have one there. All right. Let's compute it real quick here. By the formula is going to be, 59 factorial divided by 59 minus six factorial. So let's see if I can do that in Code Sculptor. 59. We'll divide that by math-factorial of 59 minus six. Run that. And out came- well that's a pretty darned big number. Let's see how many digits is that. Wow. A lot like, billions. I'm not sure I'm going to play that lottery. That lottery doesn't look very like our chances are in favor. Actually, when we did this computation in Python, something remarkable happened. Notice what happened, we computed 59 factorial first, and then did division. Well how big is 59 factorial? Well let's just, actually, we'll just cut and paste and let's just see how big it is. [SOUND] Okay. Way too many zeros. No way I'm ever playing that lottery. I mean, this is actually quite a remarkable computation. Somehow we generated this number, with, like, I don't know, 100 digits, and Python just handled it with no problem at all. In fact, Python is quite remarkable. It has a, kind of a built in capability to handle arbitrarily long integers. So, not every language has that capability, so, be happy you're working in Python. Now it turns out this computation is a little wasteful. We can we note in the notes, that really there's a, there's a term of 53 in both the numerator and the denominator and they just cancel out. The term 52 cancels out. 51 cancels out. So we could actually write some code which just really computed 59 times 58 times 57 times 56 times 55 times 54. Let's just write that code real quick. So let's call the answer. We're going to compute the number of permutations and we're going to essentially kind of build it up a multiplication at a time. So we're going to build a loop here and. Oh, no! I can feel it. You're all rooting for me to use i here aren't you? I'm going to resist the urge. I'm going to use a, a three letter, three letter index here. We'll call idx. That's about as many letters as I can spare. And we're going to do that say in the range, and let's make our range kind of go from 59, 58, downward. That's the same way our capitation works, so it be 59. To 59 minus six. We'll do [UNKNOWN] minus one. What do we need to do? We need to say the number of permutations. Let's see, times equal the index, and then I already see an error there. Let's do perms. And then we'll say print the num_perms. Now notice, if I've actually done this right, this should get, we should reproduce this number here. Check our code one more time. We're going to hit run. Yay, look at that. We ended up with the exactly same number. The key here is, we never had to do 53 divided by 53, or 52 divided by 52, or so forth. So this is a kind of trick you might want to use, if your using a language that doesn't have build in support for very large integers. All right. Let's finish off lecture. So we're going to talk a little bit about combinations. So, for permutations, the order of the sequence of outcomes was important. For combinations, order is not important; in fact, really, combination is just a set. And this mirrors a little bit what we did on the previous lecture with gen all sequences and gen assorted sequences. And the reason we could had to use assorted sequences instead of a set there is because we were allowed to repeat outcomes, so we had to use assorted sequence. Here, since we're not allowed to repeat outcomes, a combination is really just a subset of the set of all possible outcomes. It turns out there's a really simple formula for counting the number of possible outcomes. Let's just look at this example real quick here. I have two sequences, 34, 12, 27, 56, 58. Here's another one, 56, 12, 27, 34, 58. These are different permutations, but notice that really, they're the same combinations, because these two sets are equal. So when we're looking at permutations, there's kind of a collection of permutations that all correspond to the same subset of outcomes. So, really, to kind of figure out how many combinations we have we could start with all the permutations and then figure out how many kind of correspond to the same subset. And, if you look at this, in this particular case, where there are five items in the combination, there's really five factorial different ways we could order these items. So the formula for determining the number of combinations is really pretty elegant. You just take the number of permutations, this formula here, and you divide by the number of orderings. Okay? [INAUDIBLE] N, that'd be N factorial. To arrive at a formula which is, it's N factorial divided by M minus N factorial times N factorial. Okay. Let's go and just try one example real quick to see what this corresponds to in practice. So here I have my code. I've went through and I've got the number of permutations of link six by 59 lottery balls. So let's figure out how many combinations we have. So I could print the number of permutation, and divide that by; well let's see there were six balls. So I need to divide by math.factorial of six, that's actually 720. Now I'm going to run that and, see what comes out, 45 million, well alright maybe I'm going to play that lottery. So this kind of illustrates the difference between permutations and combinations. When you consider combinations, we'll get a much lower number. All right. I'll see you next lecture. [BLANK_AUDIO]
