Video Transcript
We’re gonna take a look at a few questions that use the methods of permutations and combinations in order to solve them. So the first question then: To create a password, I use two different numeric digits and six different lower case letters. How many possible unique passwords could I generate this way?
Well there are ten possible numeric digits, zero through to nine, and I’m choosing two of them and they’re different. And there are twenty-six letters to choose from and they’re all lowercase letters, but I’m choosing six from those. So for the digits, I’m choosing two from ten, and that’s gonna be ten factorial over two factorial, which comes from the two that we’re choosing times eight factorial. And that’s the difference between the two and the ten. So I could just do that on my calculator, but I’m just writing them- those numbers out in full. So ten factorial is ten times nine times eight all the way down to one, and then we’ve got two factorial and eight factorial on the bottom.
Now of course quite a few of these cancel out, so the eights cancel. Seven, six, five, four, three, two, and one cancel out, so I’ve got ten times nine over two times one. So that means I’ve got forty-five possible pairs of digits that I can generate this way. And for how many letters, how many combinations of letters I might have, that’s twenty-six 𝐶 six or twenty-six choose six, so twenty-six factorial over six factorial times the difference of those two twenty factorial. And when I work that out on my calculator, I get two hundred and thirty thousand two hundred and thirty possible sets of six letters. So I can combine all of those forty-five possible pairs of digits with all of the two hundred and thirty thousand two hundred and thirty possible sets of six letters. So that’s forty-five times two hundred and thirty thousand two hundred and thirty sets of two digits plus six letters, eight characters.
So that’s over ten million sets of eight characters that I can work with. But of course if I’ve got eight different characters, I can organise them eight factorial ways. Eight times seven times six times five and so on. And when I work that out, that’s forty thousand three hundred and twenty ways. So each one of those sets of eight characters can be arranged in forty thousand three hundred and twenty ways. So I’ve gotta multiply those two numbers together to work out the total number of different passwords I can generate. That’s quite a lot of passwords, four hundred and seventeen billion seven hundred and twenty-nine million three hundred and twelve thousand different passwords to choose from.
Right, then the next question. I take all the letters in the word randomize — and yes that’s the American spelling, so if you’re watching this in the UK, there you go. That’s how they spell it in America — and rearrange them so that the vowels are next to each other. How many different ways are there of doing this? Well let’s just write the consonants down first. So that’s R, N, D, M, and Z, and then we’ve got the vowels next. And so A, O, I, and E are the vowels. Now the question has said that we’ve gotta get the vowels all next to each other in our combinations. So what I’m gonna do is I’m gonna group those vowels together and just sort of pretend that they’re a brand new letter, a very complicated new letter. And so we’re gonna jumble up the R, N, D, M, Z, and this new imaginary letter called AOIE which is a slightly weird pronunciation, but that’s it. And let’s do some analysis on that. So I’m just gonna rephrase the question then. How many ways are there to arrange the letters R, N, D, M, Z and AOIE? So that gives me six letters to arrange in total. I may have to do a little bit of tweaking afterwards. So if I’ve got six different letters and I arrange them and they’re all different and I arrange them in different orders, there are six factorial ways to do that. I pick one and then I’ve got five to choose from. I can combine any of those six choices for the first one with the five for the second one, the four for the third one and so on. So that comes to a total of seven hundred and twenty different ways to organize those six letters.
But of course AOIE isn’t really a letter. In fact, there are four letters in here, and I need to consider all the combinations of those in different orders combined with those seven hundred and twenty different ways. So if I’ve got AOIE at the beginning, there are actually a number of different ways that I can configure the letters within AOIE, which would count towards our total number of combinations and arrangements. So hopefully we can see that we’ve got four different letters. There are four different vowels. If we want to rearrange them all in different ways that look unique, there are four factorial ways of doing that. Four choices of the first letter, three for the second, two for the third, one for the fourth and so on. So that gives us twenty-four different ways of that happening. So although we said we had seven hundred and twenty ways of arranging the six letters in each of those cases, in each of those seven hundred and twenty ways, there are actually twenty-four ways that the supposed letter AOIE can be organized. So we’ve gotta multiply those two numbers together to get our total number of combinations. And when we multiply those two together, I get seventeen thousand two hundred and eighty different ways to organize those letters, so which-in which all cases: the A, the O, the I, the E, all the vowels are right next to each other.
So our next question is I take all the letters in the word degenerate and rearrange them so that all the vowels are next to each other. How many different ways are there of doing this? Well this sounds very similar to the last question except this time the vowels we’ve got one, two, three; we’ve got four different Es and an A. So when we put those five vowels next to each other, some of the combo get- combinations are gonna be indistinguishable from each other, so we need to take that into account in our calculation. So when I look at that, I’ve got five consonants and five vowels. It was a ten letter word, and I’m gonna play the same trick again. And what I’m gonna do is actually lump all of those vowels together as if they were just one letter, because they’ve got to be next to each other according to the question.
So let’s just rephrase our question then. How many ways are there to arrange the letters D G N R T and E E E A E. Let’s treat that as one letter, so we’ve got six letters there to rearrange. And as we saw before, to arrange six unique things, what we do is we’ve got six choices for the first letter, five for the second, four for the third and so on. And they can all be combined with each other, so that’s six times five times four, six factorial ways of rearranging those six letters. That’s seven hundred and twenty different ways. Now we’ve gotta take into account the fact that that last letter isn’t in fact one letter, but it’s a combination of five different vowels. So, well, not five different vowels, but five letters. So we’ve got five vowels there. In fact, four of which are the same. So with actually five vowels, we’d expect five factorial different ways of organizing those vowels.
But remember, four of them are Es. So for every positioning of A, whether it’s first, second, third, fourth, or fifth, the other four Es are- can be rearranged four factorial ways, which we wouldn’t be able to distinguish. So that’s five factorial divided by four factorial leaves only five ways to organize the vowels in unique ways. And that make sense, either that A is first followed by all the Es or the As second surrounded by Es, the As, third the As, fourth the As, fifth and so on. So we said there were six factorial ways to arrange the six letters which gave us seven hundred and twenty ways. We then said that actually this letter here isn’t a letter, and in fact that can be rearranged five ways. So those seven hundred and twenty ways can be rearranged five ways with different- with A in these different locations as the first, second, third, fourth, or fifth. So seven hundred and twenty times five which is three thousand and six hundred possibilities in total for the ways of organizing all those letters so that the vowels are all next to each other.
Right, so we’re gonna complete our little sequence of questions with this last one which is just another slight extension of the idea that we’ve been working on. So how many different ways are there to arrange the letters of the word INSTALLATION into uniquely identifiable combinations in which the vowels all appear next to each other? So we’ve got aspects of what we’ve just been doing, but now we’ve got repeated vowels and we’ve got repeated consonants to deal with in this question. That’s a bit trickier. Now we break that down. We’ve got the N S T L L T N. We’ve got seven consonants. Okay, some of them are the same. And we’ve got five vowels again; we’ve got some repeating vowels in there, the two Is and the two As. So we can refrain that question then. The vowels must be together, so treat them as one letter. And let’s call that letter IAAIO, weird pronunciation, but there we go. How many ways to arrange the letters N S T L L T N IAAIO. So that’s eight individual letters: one, two, three, four, five, six, seven, eight that we’ve got to rearrange.
So we’re looking to arrange eight letters now. If they were unique, so they’re all different, then that would just be a straight eight factorial. But of course with two Ns, two Ts, and two Ls, well we have to approach this slightly differently. So within that eight factorial, every time you can swap over the Ns, you can swap over the Ts, and you can swap over the Ls and you’ll get different combinations in there. So we have to divide that eight factorial by two factorial to represent these two ends. Two factorial times two factorial to represent those two Ts times two factorial to represent the arrangements of those two Ls. And that gives us five thousand and forty different ways to arrange those eight letters with those particular repetitions, but of course that’s not the whole story. Because in fact within that, we can rearrange the- some of the vowels. So for each of those five thousand and forty ways, we can rearrange these five vowels. So we’ve gotta work out how many different ways could we rearrange those into unique identifiable different combinations. So let’s have a look at that.
So similarly to what we’ve just did with the eight letters, we’ve got five letters to arrange. So that will be five factorial. But remember, two of them are Is, two of them are As. So we’re gonna scale that back by dividing by two factorial for the two Is and two factorial for the two As, which gives us thirty different ways. So what we can see is that for each of those five thousand and forty different combinations of what we call eight letters, we’ve got thirty different ways to arrange the I, the A, the A, the I, and the O in uniquely identifiable different combinations. So we’ve gotta multiply those together. Five thousand and forty lots of thirty ways give us a total of a hundred and fifty-one thousand two hundred combinations of those letters to follow those rules.
So let’s just kinda summarise then what we’ve learned there hopefully. How many ways are there to arrange 𝑛 different objects? Well the answer to that is 𝑛 factorial. You’ve got a choice of 𝑛 for the first object and 𝑛 minus one for the second object, 𝑛 minus two for the third object, and so on. And how many ways are there to arrange 𝑛 objects if 𝑛 of them are the same? Well we’ve got 𝑛 factorial ways of arranging 𝑛 objects. And if 𝑛 of them are the same, then some of those are gonna be indistinguishable from each other. So we’re gonna have to reduce that total. So for example, if we had three different objects, there will be three factorial ways of organizing them. But if two of those were the same, then we can follow that same pattern, and we can see that some of those are indistinguishable. So for example, this one here and this one here look just the same. These two here look just the same and these two here look just the same. I mean if we had some way of distinguishing between those two Bs — let’s call them the first B and the second B — then we can see that these different patterns are-are different. But if you- if they’re just called B and B, then you can’t really tell those two apart: B one and B two.
So in this case, we started off with three factorial ways. But of course we’ve gotta divide that by two factorial, because there’re- you can have the B one first and the B two second, or we can have the B two first and the B one second. Obviously, if you have more of those that were the same, you would have more different ways of organizing those ones that were the same. And you’d have to divide by a bigger number. So however many are the same, that’s where this number comes from here. And the 𝑛 factorial on the top tells us the- tells us how many ways if they were all different letters, how many different ways there would have been of organizing them. We’ve also practised the permutations formula. So how many permutations for picking 𝑟 objects from 𝑛 different objects, 𝑛𝑃𝑟 is 𝑛 factorial over 𝑛 minus 𝑟 factorial. And then finally, we looked at how many combinations for choosing 𝑟 objects from 𝑛 different objects when we’re only counting combinations. So it doesn’t- we don’t count the same combination more than once if the objects are in a different order. So that’s a slightly smaller number, 𝑛𝐶𝑟 is 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial.
