Some of the most unique experiences we'll ever have might not be the foods we try, the places we go or even the people we meet. Instead, it might just be in a deck of cards. Shuffle a deck of cards reasonably well, and odds are that it'll be the first time that particular order of cards has ever existed. In fact, if we spent billions of years shuffling cards, millions of times a second, it'd still probably be the only time that combination ever comes up. It sounds unbelievable, but it turns out when we have lots of different ways we can order a collection of objects, the possibilities quickly add up, which means even seemingly simple tasks like, say, arranging a bookshelf, or even just choosing a few books, can lead us into the realm of really big numbers, but math gives us a way to make sense of all those possibilities using the concept of permutations. I'm Jason Guglielmo and this is Study Hall Real World College Math.
To see how arranging a collection of objects quickly leads to wildly large numbers and how tame them, let's meet two fictional characters, Adriana and Bisera. They've just moved into their first apartment together and are organizing their books, and at first it seems pretty simple. Between them, they only have 10 books to arrange on a shelf which we are going to refer to as books A through J. They also have pretty different opinions on how to arrange their books. Adriana pitches something organized and functional, like alphabetic order by the author's last name. But Bisera is feeling something more visually appealing, like organizing by the color of the spines. They try both and decide that neither feels quite right so they opt to spend the afternoon experimenting with all the different possible arrangements of their books to find the one that they both like.
Using the same letters we assigned, they start off with the following order from left to right. Then they try moving one book around. Of course, they could keep moving that book around but the other books are all still in the same order so they try moving another one too. When we move items around like this, we're creating new arrangements of them and in math these arrangements where we're specifying the order of a group of objects have a particular name: permutations. Specifically a permutation is an arrangement of objects where the order the objects are in matters. So as Adriana and Bisera shuffle or permute their books, they keep track of every permutation and how much they both like it, exploring all of the options but it seems to be taking, like, a long time. They quickly begin to wonder how many total different permutations exist for these 10 books. Little do they know, there are 3,628,800 possibilities. So trying out each one could take a while. That's a lot of possible orders for just 10 books.
To figure out where that number comes from, let's think about our permutations in a more structured way. On our shelf, there are 10 possible positions or places for a book to be, because there's 10 books and each book ends up with a particular place in the order. Now, we almost always visualize the order of permutation from left to right, but all of the math still works if we think right to left or top to bottom or whatever. Let's think about that first position.
Because we have 10 books, for each permutation there are 10 possibilities for which particular book will go in that first position. Let's assume we pick a particular book to go in that place, say book C. Now we have nine positions left and nine books because we already placed one. So, for our second position, we now have nine possibilities for the book that could go there. And just like before, we can choose a book from the nine we have left, say book G. Once again, we end up with one fewer position to fill and one fewer book to find a spot for. So now we'll have eight possibilities for the third position. A pattern is starting to emerge. Every time we choose a book from our list to fill a position, we end up with one fewer choice for the next positions. That same pattern will keep going on until we have just one position and one book left. So we know the number of options we have for every individual spot on the shelf. When we're trying to permute or arrange 10 objects, we have 10 possibilities for the first item, then nine for the second item, because something had to go in the first spot, then eight for the third, and seven for the fourth, and so on until we have just one thing left for that last position.
If you watched our last episode on counting, this might be starting to sound familiar. In order to find the total number of possibilities, we can use this information in an important counting tool called "The Fundamental Counting Principle." The fundamental counting principle tells us that when we have a set of choices for an event and another set of choices for a second event, the total number of ways the two events can happen together comes from multiplying the number of choices for the first event by the number of choices for the second event and we can extend this to any number of events. In this case, our first event is filling the first spot on the shelf. The second event is filling the second spot on the shelf and the third is filling the third spot and so on. And we've just worked out the number of choices for each of those positions. So, using the fundamental counting principle, the total number of options, which in our case means the different permutations or ways we can put the books on the shelf, comes from multiplying all of those numbers. That's 10 times 9 times 8 and so on, all the way to 1, which is 3,628,800.
What's more, the fundamental counting principle tells us this would work just as well if we had some other number, like five, books. Then the total number of permutations would be 5 times 4 times 3 times 2 times 1, since we'd have five items to arrange and five places in the permutation. In fact, this gives us a general formula for figuring out the total number of possible permutations given any number of objects which we'll just label N to avoid saying number of objects over and over. For N distinct objects, the number of different ways of arranging them equals N times N minus 1 times N minus 2 all the way down to times 1, which, remember, comes from just having one object left to put in the last spot.
This sort of pattern where we start with a number and multiply it by all of the positive whole numbers after it down to 1 comes up all over the place in math and it has a special name: a Factorial. We represent it by showing the original number of items being arranged, followed by an exclamation mark. For instance, the number of ways of arranging our 10 books is 10 factorial. So another way to put our formula is that for N items, we have N factorial possible permutations. So for four books we'd have four factorial possible permutations, which is 24 and for three we'd have 3 factorial, which is 6. But let's think about cards again, for a standard 52-card deck used for card games, 52 factorial is about 80 trillion, trillion trillion, trillion, trillion, million possibilities. That's an 8 followed by 67 zeros, which is why a well shuffled deck is extremely likely to be unique.
Thinking through permutations can even work in some special cases, like if Adriana and Bisera had no books to put on the shelf. According to the formula we just created, that's zero books which is 0 factorial, but now we're in a bit of a bind. Our factorial formula is supposed to end with 1 but 0 is already less than 1. So our formula doesn't really work in this case. Well, if we have zero items, there's really only one way to arrange nothing. Our only option is to put nothing there. So we say that 0 factorial equals 1. As for our bookshelf, overwhelmed by the millions of possibilities, Bisera and Adriana decide just to organize them by genre, a happy compromise.
Meanwhile, their close friend, Chandrak, who works for a book review magazine, has run into his own book-related permutation problem. The magazine has put together a shortlist of the 10 best books from the last year to be voted on by the public for their hotly anticipated annual book awards. The three books with the highest votes get featured on the front cover and the authors win different prizes for first, second, and third place. If Chandrak can mock up front covers for every potential vote outcome then the magazine can publish the results as soon as the voting closes, based on whichever combination of the three books wins first, second, and third place. That sounds great, but he might be running into a situation like Adriana and Bisera with millions of possibilities. So to see if this is feasible, Chandrak first needs a way of determining how many permutations of three books are possible, but from a selection of 10 overall books to choose from.
Just like before, we have 10 possibilities for books in the first place. Having selected first place, there are 9 options left for second place and then 8 for third place. But that's where we stop because we don't care about the order of the seven remaining books. So the total number of possibilities is just 10 times 9 times 8, which is 720. There's another way to think about our answer. We have 10 items, and the start of our answer looks a lot like 10 factorial but after three positions, we stop, and all the terms from 7 onwards are missing in our multiplications. That's the same as taking 10 factorial and dividing the whole thing by 7 factorial in order to eliminate the terms we don't need. In fact, this gives us another tool for dealing with permutations. When we only want the number of permutations for a certain number of objects, which we usually call K, out of our total larger number of objects, N, then following the exact same reasoning as our book contest, we can write down a general formula. Our new formula is basically the same as the factorial formula with all of those repeated multiplications, but we chop off the bit which looks like N minus K factorial because we're ignoring N minus K of the objects and only choosing K of them. And because mathematicians love abbreviation, we can write this as nPk, where the P stands for permutation and is capitalized to distinguish it from the numbers. We also use the letter K here but you might also see the same formula as nPr. It's the same thing.
As for Chandrak, although 720 is certainly much less than a few million, it's not worth the trouble of mocking up hundreds of different covers. With that, we can now count all the ways of ordering all the objects in a collection and all the ways to arrange a smaller set of objects from within a bigger collection. And those are incredibly powerful tools because whether we're looking at books, mathematical objects like polynomials, or even, as we'll see in future episodes, outcomes of probability experiments, when we have any collection of things with an inherent order to them, there's always a whiff of a permutation about, so with permutations in their formulas in our toolbox of math ideas, we can often take the first step to understand how all that shuffling around affects the things we're interested in or helps us decide what order best suits the task at hand whether it's mind bogglingly large possibilities or just exploring some options.
Next time, we'll use our knowledge of permutations to arrange things when the order doesn't matter with combinations.
Thanks for watching Study Hall Real World College Math which is produced by Arizona State University and the Crash Course team at Complexly. If you like this video, give us a like and subscribe. You can learn more about ASU and the videos produced by Crash Course and the links in the description. See you next time.