In Part I of this article, we described how to calculate the number of combinations of a combination lock, as well as the number of ways to arrange objects, instead of listing out each combination individually. In Part II, we will continue to discuss other ways to arrange objects.
Chapter 1: Permutations
In Part 1, we discussed how seven prizes may be awarded to seven boys that are competing in a race. However, it is not common to award so many prizes in actual races. In most sports competitions, prizes are only awarded to the top 3 contestants. How many ways are there to award three prizes to seven competitors?
We can still use the method of finding how many possible choices there are for the first place, second place and third place:
For the first place, any of the seven competitors can win, thus there are seven choices;
For the second place, any of the six remaining competitors can win;
For the third place, any of the five remaining competitors can win;
Thus, the number of ways to award three prizes to seven competitors is equal to:
Number of ways = 7 × 6 × 5 = 210.
More generally, how many ways are there to award r prizes to n competitors? For the first place, there are n choices, for the second place, there are n – 1 remaining choices, for the third place, there are n – 2 remaining choices.
Thus, the number of ways is equal to n x (n –1) x (n – 2) x … x (n – r + 1). Note that there are exactly r integers between n and (n – r + 1).
This formula can be more concisely written as
since n! = n x (n –1) x (n – 2) x … x (n – r + 1) x (n – r) x (n – r – 1) x … x 1 and (n – r)! = (n – r) x (n – r – 1) x … x 1
nPr is read as “n permute r”, which refers to the number of ways to select an ordered group of r distinct items, from a group of n distinct items. It is the same as the number of ways to arrange n items, given that all the items other than the first r items are similar, as is the case in this example, where the order of competitors finishing after the third competitor does not matter, as they will not win a prize anyway.
Test Your Knowledge (Part 1)
1. At a music competition, there are ten competitors. Each judge ranks the top four competitors of their choice. How many ways are there for a judge to choose the top four competitors out of ten competitors?
Answers to Test Your Knowledge (Part 1)
1. Number of ways = 10P4 = 10!/(10-4)! = 10 × 9 × 8 × 7 = 5040.
Chapter 2: Choices
We are blessed with choices in many aspects of life. We can choose what we want to eat at a restaurant, or how we can spend our time each day.
Korean restaurants are famous for providing a wide variety of side dishes to customers. At the local Korean restaurant, ordering a meal will allow you to choose from any five of the ten side dishes, which will be served with your meal. How many ways are there to choose five side dishes from a menu of ten side dishes?
Isn’t this the same as the number of ways to award five prizes to ten competitors, which is to say, 10P5 = 30240 ways?
Actually, it is not. When awarding five prizes to ten competitors, the order in which prizes are awarded is important. When choosing side dishes, the order in which you choose is not important, since all the side dishes will be served at the same time anyway.
If the order which you chose the side dishes were important, then the number of ways to choose would indeed be 10P5 = 30240. However, because five side dishes can be ordered in 5! = 120 ways, we must then divide by 120, since the order does not matter. Thus, the number of ways = 30240/120 = 252. When choosing r objects from a group of n objects, where the order does not matter, the number of ways to choose is equal to n!/(r! x (n – r)!). This is equivalent to nPr divided by r!, since the order of the choices do not matter.
The number of ways to choose r objects from a group of n objects, where the order does not matter, is written as nCr, where
Thus, choosing five side dishes from a group of ten side dishes can be written as 10C5.
It is important to know when to use permutations and when to use combinations: use permutations when order matters, and combinations when the order does not matter.
Test your Knowledge (Part 2)
2A. Bob’s school allows him to choose from 4 educational activities and 4 fun activities during the holidays. However, his mother insists that he must go for all 4 educational activities, and none of the fun holiday activities. How many ways are there for Bob to choose 4 educational activities and 0 fun activities, where the order that Bob chooses does not matter?
2B. When making a stew, a chef places some ingredients in a pot and then mixes all the ingredients together when cooking. A chef wants to choose 5 different spices from a bag of 12 spices to add to his stew. How many different ways can he do so?
2C. A cloze passage has several blanks, as well as different helping words to choose from, to fill in the blanks. A student did not study for his language exam, and has no idea what any of the 8 helping words mean. How many ways can he randomly guess the answers to the 5 blanks in the cloze passage, if each helping word can only be used once?
Answers to Test Your Knowledge (Part 2)
2A. Number of ways to choose 4 educational activities = 4C4 = 4!/(4! × (4 – 4)!) = 1
Number of ways to choose 0 fun activities = 4C0 = 4!/(0! × (4 – 0)!) = 1
When you have to choose all of the objects in a group, or none of the objects in a group, then you only have one choice. That is to say, that nCn = 1 and nC0 = 1. Imagine a situation where the choice is made for you. That would be very sad indeed.
2B. Since the ingredients are going to be stirred together, the order of adding the spices does not matter. Thus, the number of ways to choose is 12C5 = 12!/(5! × (12 – 5)!) = 792.
2C. The questions are different, and thus the order of filling them in does matter. (If you fill in question 2 with the answer to question 1, and vice versa, then you will get both questions wrong). Since order matters, we have to use permutations and not combinations.
The number of ways to choose is 8P5 = 8!/(8 – 5)! = 6720.
