Video: Permutations and Combinations Part 2

Video Transcript

In part one, we looked at how to count up the number of ways to arrange objects and use the factorial notation to produce a formula for this. We also looked at counting how many ways there are to pick a certain number of objects from a set and came up with the permutations formula, 𝑛 𝑃 𝑟. Now we’re gonna use these things to count combinations of objects where their order isn’t relevant and we’re gonna use the combinations formula, 𝑛 𝐶 𝑟 in a few examples.

So remember, we learned last time that 𝑛 factorial means 𝑛 times 𝑛 minus one times 𝑛 minus two, and so on and so on, times three, times two, all the way down to times one. So, for example, five factorial means five times four times three times two times one. And we also learned the formula 𝑛 𝑃 𝑟, permutations formula, is equal to 𝑛 factorial over 𝑛 minus 𝑟 factorial, so we’re picking 𝑟 objects from a set of 𝑛 objects. Now we did say that zero factorial is equal to one. So if 𝑛 and 𝑟 turn out to be equal, it would mean that with zero factorial on the bottom, we’d just make that equal to one. Well an example of that is in the question how many ways are there to pick three letters from the letters 𝐴, 𝐵, 𝐶, 𝐷.

So in this case 𝑟 would be equal to three cause that’s the number of letters we’re choosing, and 𝑛 would be equal to four cause that’s the size of the set of letters that we’re choosing from. So 𝑟 would be three because that is the number of letters we’re choosing, and 𝑛 would be equal to four because that’s the size of the set of letters that we’re choosing from. So the answer to the question would be four 𝑃 three, so that’s four factorial over four minus three factorial, which of course is four factorial over one factorial. And when we worked that out, we get an answer of twenty-four. So the important thing about this is that the order of the letters was quite important because that twenty-four combinations there includes all of these ones here. And these are basically all variations on 𝐴, 𝐵, and 𝐶, so just add the letters 𝐴, 𝐵, and 𝐶 in different orders. If it doesn’t matter to you what order they’re in, effectively we can count all of those different combinations as one choice, just one option. And it’s that process that we’re going to look at in this video.

So, as we’ve just seen, 𝑛 𝑃 𝑟 tells us how many permutations there are for picking 𝑟 objects from a set of 𝑛 objects. And again, as we’ve just seen, each group of 𝑟 letters — so we have three letters in that example 𝐴, 𝐵, and, 𝐶 — is written 𝑟 factorial different ways. So three factorial different ways. That’s three times two times one is six different ways in the big list. So that big list contains a lot of repeats if you’re not really interested in what order they appear in. So we’re gonna look at how to work out how many different combinations we get when choosing 𝑟 objects from set of 𝑛 objects if we discard all the different rearrangements of the same letter. So 𝑛 𝑃 𝑟, as we’ve said, told us how many unique permutations we had, and that list included 𝑟 factorial repeats of groups of three letters. So if we just want to know for example how many groups of three letters, or 𝑟 letters, that we’ve got in a final answer, then what we need to do is take the answer 𝑛 𝑃 𝑟 and divide it by 𝑟 factorial. So there we are, 𝑛 𝐶 𝑟 is 𝑛 𝑃 𝑟 divided by 𝑟 factorial. So the formula for 𝑛 𝑃 𝑟, remember, was 𝑛 factorial over 𝑛 minus 𝑟 factorial. If we divide that by 𝑟 factorial, then it’s the same as multiplying by one over 𝑟 factorial and that gives us this formula here, 𝑛 factorial over 𝑟 factorial 𝑛 minus 𝑟 factorial. So remember, 𝑛 𝑃 𝑟 counts the permutations where different orders of the same group of letters count separately, so we’ve kind of kept double, triple, quadruple counting things and so on. And 𝑛 𝐶 𝑟 counts the combinations where different orderings of the group are combined together. So in our last example, all the 𝐴𝐵𝐶, 𝐴𝐶𝐵, 𝐵𝐴𝐶, and so on, that would count as multiple permutations in the 𝑛 𝑃 𝑟 formula, but we would count all six of those variations just as one combination in the 𝑛 𝐶 𝑟 formula because they are all the same group of three letters.

Right, let’s have a look at a couple of examples then. So if we’ve got ten discs labelled 𝐴 up to 𝐽, we take three discs at random and set them down in the order that they were selected. How many permutations are there for this? So 𝑛 would be ten in this case because we’ve got a set of ten letters to choose from. And 𝑟 will be three because we’re picking three from that set. Now we’re setting them down in order, so 𝐴𝐵𝐶 for example would not be equivalent to 𝐶𝐵𝐴 and so on, so we want to use the 𝑛 𝑃 𝑟 formula.

And substituting in those values for 𝑟 and 𝑛, we’ve got ten 𝑃 three, so that’s ten factorial over ten minus three factorial. And that gives us ten factorial over seven factorial. Now, obviously, we could just put that in our calculator and get our answer, but I’m just gonna write that out in full for a moment. And when we do that, we can see that we can do quite a lot of cancelling. So seven divided by seven is one, six divided by six is one, five divided by five is one, four divided by four is one, three divided by three is one, and so on. All of those cancel out, so we’re ending up with just ten times nine times eight over one or just ten times nine times eight. So that gives us seven hundred and twenty different permutations that we can get. So that’s our answer. Now, just to sort of highlight the difference between 𝑛 𝑃 𝑟 and 𝑛 𝐶 𝑟, remember that seven hundred and twenty includes for every set of three letters like 𝐴𝐵𝐶; we’ve got six variations on that in there. And if we’re prepared to say that they’re all equivalent cause they’re just combinations of the letters 𝐴, 𝐵, and 𝐶, we can divide that seven hundred and twenty by six, in this case, three factorial because we had 𝑟 was equal to three to work out the number of combinations. So there’s the calculation then for 𝑛 𝐶 𝑟. If we were looking for how many clusters of three letters, the answer would only be a hundred and twenty. But the question specifically asked for permutations and it said that the order was important, so we settled down in the order that they were selected. So this is the correct answer.

Just make sure that, on the page, we’ve got the-the proper correct answer highlighted, and it’s obvious that this other working out wasn’t just another guess of what the answer might be. Okay, let’s look at this small essay for our next question. In a lottery, we choose five letters of the alphabet. During the draw a machine loads twenty-six balls, each way- each one has one of the letters 𝐴 to 𝑍 on them. It shuffles them and then it lets out five. It doesn’t matter what order they were drawn in if our five chosen letters match the machines, then we win! How many combinations of five letters are there to choose from? So in this case the order doesn’t matter, so we’re gonna be using the 𝑛 𝐶 𝑟 combination. And there are twenty-six letters of the alphabet to choose from, so 𝑛 is equal to twenty-six. And we’re choosing five of those letters, so 𝑟 is equal to five. So we’re choosing five, 𝑟 equals five, from twenty-six, 𝑛 equals twenty-six. And it doesn’t matter what order they were drawn in, so we’re using the 𝑛 𝐶 𝑟 formula which is twenty-six 𝐶 five when we plug those values in for 𝑛 and 𝑟. So that gives us twenty-six factorial over five factorial twenty-six minus five factorial, which is twenty-six factorial over five factorial twenty-one factorial. Now again we can just plug this number into a calculator and get our answer, but I’m just gonna take a little extra step here and just kind of split this out slightly. Sometimes the numbers that you get are too big to work on a calculator; but by spotting some things that you can cancel, you can actually generate numbers which are small enough that your calculator can still handle. And that’s, well, that’s not the case here. We can, you know, this-this number would work on a calculator, but let’s see the technique anyway. So haven’t quite got room to write out twenty-six factorial in full but I know it’s twenty-six times twenty-five times twenty-four times twenty-three times twenty-two times twenty-one, and so on and so on. But of course this bit here, twenty-one times all the numbers down to one, is just twenty-one factorial. So we’ve got this stuff here, times twenty-one factorial on there-on the top and on the denominator. We’ve got a twenty-one factorial, so in fact these twenty-one factorials will cancel out. So we’ve got this divided by five factorial. So sixty-five thousand seven hundred and eighty, that’s the number of combinations that are there. So if this whole thing was done at random, that’s the number of different ways there are of choosing five letters, so we’ve got one in sixty-five thousand seven hundred and eighty chance of winning this particular lottery. Now as a bit of an aside, if it did matter, if we had to match the order in which the letters came out as well, we would’ve used the 𝑛 𝑃 𝑟 formula. And of course we’ve got groups of five, so that’s gonna five factorial sort of different combinations of each grouping of five letters, so the answer is gonna be five factorial times bigger than that: seven million eight hundred ninety-three thousand six hundred. So actually you’ve got a far smaller chance of winning that particular lottery if it does matter what order the balls came out in, but of course that’s not the answer we were looking for in this particular case.

Okay, finally then, let’s just use our combination counting techniques to calculate some probabilities. So we’ve got a question here. A bag contains five chocolate and fifteen strawberry sweets. If someone chooses a sweet at random, find the probability that they pick a chocolate one; and if two people choose a sweet, each at random, find the probability that they both get chocolate. So really we’ve got two questions, let’s call them 𝐴 and 𝐵. Let’s look at the first one first. Someone chooses a sweet at random, find the probability it’s chocolate. Well, this is pretty straightforward. The probability you get a chocolate sweet is just the number of ways of getting a chocolate sweet divided by the number of ways of choosing a sweet of any sort. And of course there are five chocolate sweets and then there are fiv- fifteen strawberry sweets, so it’s five divided by five plus fifteen, so that’s five over twenty. So our answer, the probability of getting a chocolate sweet, is just five over twenty. Okay, let’s look at the second question. Now we’re going to look at two different methods of doing this question. The first method, which is maybe the one that you’ve already thought of, we’ve got two events. So first of all person one gets a chocolate sweet and then person two gets a chocolate sweet. So for those two things to happen together, we have to have one and the other, we’re going to multiply those probabilities together. So we’ve just worked out that the probability of one person getting a chocolate sweet is five over twenty. And of course if they’ve picked a chocolate sweet, one, there’s just gonna be four chocolate sweets left, and the other thing, there’ll now only be nineteen sweets in total for them to choose from. So we’re gonna end up with five-twentieths as the probability of the first person getting chocolate and four-ninetieths as a probability of the second person getting a chocolate. Multiply those two together, do a bit of cancelling, and we get one over nineteen. Again, in probability, you’re not gonna get penalised if you don’t cancel those numbers down. But in this case, this three hundred and eighty, has may be lost a little bit of its meaning, so it’s probably more sensible to cancel down to those nice and simple numbers, one over nineteen. So method two then, the probability they both get chocolate is the number of ways that two people can choose chocolate divided by the number of ways that two people can just choose any sweet. So the number of ways that two people can choose chocolate is five 𝐶 two which would be choosing from five chocolates, and there’s two of them, so five 𝐶 two is that. And the number of ways that they can choose a sweet, but we’ve got twenty sweets in total and there’s two of them choosing, so the total number of combinations of ways they can choose is twenty 𝐶 two. And if you do this on your calculator, five 𝐶 two turns out to be ten and twenty 𝐶 two turns out to be a hundred and ninety, which reassuringly when we cancel down we get the same answer as we did the other way, one over nineteen. So there’s a one in nineteen chance that both of them will get chocolate.

So just to summarise what we’ve learned over the course of these two videos, we’ve learned about 𝑛 factorial, which has got different ways of expressing it, but it’s 𝑛 times the number one smaller times the number one smaller, and so on and so on, until we get down to one. And remember, we’ve got that special definition of zero factorial is actually equal to one; so not entirely intuitive, but you have to remember that. We’ve learned about permutations, so 𝑛 𝑃 𝑟 and the various different ways of notating that in different regions, 𝑛 factorial over 𝑛 minus 𝑟 factorial. Now this counts every different rearrangement of the same groupings as letters as individual cases, so we get quite a large number in that case. But if we want to merge together all different arrangement of the same letters that we’ve chosen and get a smaller answer, we have to divide that by 𝑟 factorial. And because we’ve got all those repeats of the same combinations of those letters or objects, we get combinations; we get the 𝑛 𝐶 𝑟 formula. And there’s different ways again of notating that, and that gives us the formula 𝑛 factorial over 𝑟 factorial 𝑛 minus 𝑟 factorial.