Chapter 1: What is Combinatorics?
Have you ever used a combination lock before? Two of the most common combination lock designs are shown below.
For Combination Lock A, there are 8 buttons labelled 1 through 8. Each button is labelled from 1 to 8. To open this lock, the buttons corresponding to the password must be pushed down, while all the other buttons must be left alone. For Combination Lock B, there are three dials each with ten digits, from 0 to 9. To open this lock, each dial must be turned to the correct digit. If you forgot your password, which lock, A or B, would require more attempts to open?
Let’s start by examining Combination Lock B. We can try writing out all the possible combinations to be attempted:
000, 001, 002, 003, 004, 005, 006, … 997, 998, 999
You can quickly observe that the combination for Lock B forms a three-digit number from 000 to 999. Thus, there are 1000 possible combinations to be attempted. A good way to understand this is by considering the possible combinations for each reel: since each reel has 10 possible numbers, there are 10 possible combinations.
Each reel can be set independently of the others, as the movement of one reel will not affect the others. The total number of combinations of the lock can be found by multiplying together the number of possible combinations of each reel. There are 10 possible combinations in reel 1, 10 possible combinations in reel 2, and 10 possible combinations in reel 3.
Number of combinations for Combination Lock B = 10 × 10 × 10 = 1000
How about Combination Lock A? There are 8 buttons, which can be either “up” or “down”. Thus, there are two possible combinations of each button, and there are 8 buttons.
Number of combinations for Combination Lock A = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256
Test Your Knowledge (Part 1)
1A. The company making Combination Lock A wants to make it more secure than Combination Lock B. They want to design another combination lock similar to Combination Lock A, but with more buttons. What is the minimum number of buttons needed so that this lock has more possible combinations than Combination Lock B?
1B. To prevent his lunch from getting stolen, Bob creates a strange combination lock, which has features of Combination Lock A and B: There are two reels, which can be set to any digit from 0 to 9. There are also four buttons, which can be either “up” or “down”. How many possible combinations does this lock have?
Answers to Test Your Knowledge (Part 1)
1A. With extra buttons, we just further multiply by 2.
Currently, with eight buttons, there are 256 possible combinations
With nine buttons, there will be 256 × 2 = 512 possible combinations.
With ten buttons, there will be 512 × 2 = 1024 possible combinations, which is more than the 1000 possible combinations of Combination Lock B. Thus, 10 buttons are needed.
1B. The two reels each have 10 possible combinations, while the four buttons each have 2 possible combinations. Thus,
Number of combinations = 10 × 10 × 2 × 2 × 2 × 2 = 1600.
Chapter 2: Arrangement of Different Objects
In the first chapter, we discussed how to calculate the number of possible combinations, when the objects can be set independently of each other. However, in many real-life situations, later choices are dependent on earlier choices. Let us consider this example: Three children, Bob, John, and Samuel, are running a race. How many ways are there to distribute the first, second, and third prize to the three children?
You may think the number of ways is just 3 × 3 × 3 = 27, since there are 3 prizes for the 3 boys to win. However, this is incorrect, as the possible people that win the second prize is dependent on who wins the first prize: if Bob wins the first prize, then he cannot also win the second prize.
We may try listing all the different possible situations:
| First prize | Second prize | Third prize |
| Bob | John | Samuel |
| Bob | Samuel | John |
| John | Bob | Samuel |
| John | Samuel | Bob |
| Samuel | Bob | John |
| Samuel | John | Bob |
There are six possible combinations in total.
Listing out all the possible combinations is a very time-consuming method. If there were seven children instead of three, there would be 5040 possible ways they could be awarded seven prizes. It would take many hours to list them all by hand.
The number of combinations can actually be calculated mathematically. Consider the following: Anyone can win the first prize, but whoever wins the first prize cannot win the second or third prizes, and whoever wins the second prize cannot win the third prize either.
Therefore, there are three possible people that win the first prize, but only two possible people who win the second prize, and only one possible person that can win the third prize. Thus the total number of possible combinations is 3 × 2 × 1 = 6.
We can extend this to any number of competitors: If there are seven competitors, then there are seven possible winners for the first prize, six possible winners for the second prize, and so on until there is only one possible winner for the seventh prize. Thus, for seven competitors, the total number of possible combinations is 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040.
Mathematicians have a special way of writing this: If I want to describe this expression
n × (n-1) × (n-2) ×… × 1
I can write it as n! (pronounced as “n factorial”). Thus, 3! = 3 × 2 × 1 = 6, and
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040. In fact, if I want to arrange n different objects in a line, there are n! possible ways to do so.
Test your Knowledge (Part 2)
2A. How many ways can I arrange six different books in a row?
2B. Despite the new combination lock that Bob designed in 1B, his lunch was still stolen by someone who managed to guess the combination. Frustrated, Bob thus decides to design another lock. Each lock has two reels, which can be set to any letter of the alphabet from A to Z, and two buttons which can be either “up” or “down”. Bob locks his lunchbox with five of these locks, each having their own password, and the locks have to all be solved correctly and opened in the correct order for the lunchbox to open. How many possible ways can a thief guess the combination to open the lunchbox?
Answers to Test Your Knowledge (Part 2)
2A. Six different books can be arranged in 6! ways, which is equal to 6 × 5 × 4 × 3 × 2 × 1 = 720 different ways.
2B. Each lock has 26 × 26 × 2 × 2 = 2704 combinations, since there are 26 possible combinations for the two reels and 2 possible combinations for the two buttons. Since there are five locks, there are 2704 × 2704 × 2704 × 2704 × 2704 = 144555105949057024 possible combinations. Additionally, since the locks have to be solved in the correct order, there are
5! = 5 × 4 × 3 × 2 × 1 = 120 possible different orders that the locks can be solved, of which only one is correct. Therefore, there are 144555105949057024 × 120 = 17346612713886842880 possible ways to guess the combination.
Chapter 3: Arrangement of Repeated Objects
How many possible ways can I rearrange the letters in the word “BANANA”? You might say that since there are six letters, then there are 6! = 720 ways of arranging the letters in the word “BANANA”. However, this is incorrect.
In earlier examples, all the objects used were different from one another. However, in the word “BANANA”, there are three As and two Ns which are identical. If the As and Ns were different, then there would indeed be 720 ways to arrange six letters. However, three different As can be arranged in 3! = 6 ways, and two different Ns can be arranged in 2! = 2 ways, while three similar As or two similar Ns can only be arranged in one possible way. Thus, we must divide 720 by 3! and then divide again by 2! to find the number of ways to arrange the letters in the word BANANA:
Number of arrangements = = 60 possible arrangements.
Likewise, if we want to find the number of ways that we can rearrange the letters in the word “SESSION”, we first start by counting the number of letters: there are seven letters, which can be arranged in 7! = 5040 ways.
Since there are three identical letters S, which could have been arranged in 3! = 6 different ways if they were different letters, we must then divide 5040 by 6 to find the number of ways to arrange the letters in the word SESSION.
Number of arrangements = = 840 possible arrangements.
Test your Knowledge
3A. With the help of his new lock, Bob’s lunch is finally safe from thieves. He opens his lunchbox to find PIZZA and CHOCOLATE. How many ways can you rearrange the letters in PIZZA? How about CHOCOLATE?
Answers to Test Your Knowledge
3A. There are five letters in PIZZA, but there are two identical letters Z. Thus the number of arrangements is 5!/2! = 60 possible arrangements.
There are nine letters in CHOCOLATE, but there are two identical letters O and two identical letters E. Thus the number of arrangements is 9!/(2! × 2!) = 90720 possible arrangements.
