Word Problems About Combinations
In mathematics, combination and permutation problems deal with counting the number of ways to form smaller sets out of larger sets, with and without regard to the ordering of the elements. "Combinations" are counted ignoring order, while "permutations" do take order into account. Math problems involving codes, tournaments, distributing items fairly, arrangements, probability, logic problems and more can be solved with combinatorial math. Here are several examples of word problems involving combinations and permutations with their solutions.
(1) Keypad Code Lock -- Easy
An electronic keypad lock opens with a seven-digit numerical string chosen by the owner. However, only a subset of all the possible 7-digit numerical strings can be set as the unlocking code. A valid code must satisfy the following conditions:
- The first digit cannot be "1."
- The last digit cannot be the same as the third digit.
- The sixth digit must be odd.
How many possible unlocking codes are there? Does this lock admit more valid codes than a six-digit lock with no restrictions?
Solution: This is a counting problem that can be worked out systematically by determining the number of possible digits in each position and multiplying to get the total number. Let's look at the digit positions one by one.
- First digit: In this position we can have 0, 2, 3, 4, 5, 6, 7, 8 or 9. This is nine possibilities.
- Second digit: In this position we can have 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. This is ten possibilities.
- Third digit: Same as second digit, ten possibilities.
- Fourth digit: Same as second digit, ten possibilities.
- Fifth digit: Same as second digit, ten possibilities.
- Sixth digit: In this position we can have 1, 3, 5, 7, or 9. This is only five possibilities.
- Seventh digit: In principle it can be 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9, which is ten possibilities, but it can't be whatever the third digit is. This reduces the number of options from ten to nine.
Multiplying 9 x 10 x 10 x 10 x 10 x 5 x 9 gives us a total of 4,050,000 different valid codes. A six-digit keypad lock with no restrictions has 10^6 = 1,000,000 different valid codes. So, even with all the restrictions this seven-digit lock has more possibilities than a six-digit keypad lock.
(2) Card Game Tournament -- Medium
Tarts is a three-player card game similar to hearts. A group of eight friends want to have a round-robin tournament to decide who is the best tarts player among them. Round-robin in this context means each person plays each possible pair of opponents once. How many matches need to be held to conduct a fair round-robin tournament? How many times does each person play?
Solution: This problem is simply finding the number of ways to make a subset of three elements out of a set of eight elements. You can use the shortcut combination formula if you already know how to solve these problems, or you can work it out the long way.
In any group of three players, there are eight ways to choose the first member, seven ways to choose the second member, and six ways to choose the third member. Multiplying gives you 336. But, this number is not the final answer because this way of counting considers different orderings of the same players to be distinct sets.
If there are three players A, B, and C, then there are six ways of ordering them: ABC, ACB, BAC, BCA, CAB, and CBA. For this word problem, all of these are equivalent. In the 336 groupings calculated above, each group of three is counted six times, over-counted by a factor of 6. Thus, the true number of different groupings is 336/6 = 56.
Therefore, the eight friends need to hold 56 different matches to ensure that every possible grouping of three plays a game of Tarts.
How many games does each participate in? For any person there are seven ways to choose her first opponent and six ways to choose her second opponent. Since the order in which the opponents are chosen doesn't matter, there are (7 x 6)/2 = 21 ways to choose two opponents out of a group of seven. Thus, each player plays in 21 matches.
(3) Keypad Code Lock -- Medium
A different brand of electronic keypad lock opens with a seven-digit numerical string chosen by the owner, but this one has different restrictions on the codes. The restrictions are
- Exactly one of the digits must be "4."
- Exactly one of the digits must be "5."
How many different valid codes are there?
Solution: To solve this problem we first analyze the number of placements of the 4 and 5. There are seven choices for where to place the 4, and then six remaining choices for where to place the 5. Seven times six is 42, and since order does matter in this problem we do not need to divide 42 by anything to correct an over-count. So there are 42 different classes of valid code as determined by the placements of 4 and 5.
For each of the 42 classes of valid code, there are five remaining positions to fill in with digits. Each of these positions can be filled with 0, 1, 2, 3, 6, 7, 8 or 9, i.e., there are eight possibilities for each slot. Thus, there are 8^5 = 32,768 different ways to fill the five slots.
Finally, there are 42 x 32768 = 1,376,256 different valid codes that can be programmed into this keypad lock. Compared to the lock in the first problem, this one admits fewer valid codes, about 1/3 as many.
(4) Invented Language -- Medium
Molly is inventing a language that consists of only of four-letter words using the consonants B, D, F, J, K, L, M, N, R, S, T, and Z and the vowels A, E, I, O, U. The words must follow one of three patterns
- vowel - consonant - consonant - vowel
- vowel - consonant - vowel - consonant
- consonant - vowel - consonant - vowel
In the first pattern, the two consonants must be different. How many different words are there in Molly's language?
Solution: This language has 12 consonants and five vowels. In the first word pattern there are five choices for the first letter, 12 for the second, 11 for the third, and five for the last. This gives a total of 5 x 12 x 11 x 5 = 3300 different words.
In the second word pattern there are five choices for the first letter, 12 for the second, five for the third, and 12 for the last. This gives a total of 5 x 12 x 5 x 12 = 3600 different words. By virtually the same argument there are also 3600 different words following the third pattern.
Therefore, Molly's language has a total of 3300 + 3600 + 3600 = 10500 words.
(5) Lights on a String -- Hard
Ava has a string of 20 lights that is missing all of the colored bulb covers. She later finds 12 blue bulb covers and 12 yellow bulb covers to put over the lights. Assuming same colored bulb covers are not distinguishable, and assuming the two ends of the light string are distinguishable, how many different blue-yellow patterns can she make?
Solution: Since the total number of bulb covers exceeds the number of lights, there are several cases that need to be analyzed separately:
- Case 1: She uses 12 blue and 8 yellow.
- Case 2: She uses 11 blue and 9 yellow.
- Case 3: She uses 10 blue and 10 yellow.
- Case 4: She uses 9 blue and 11 yellow.
- Case 5: She uses 8 blue and 12 yellow.
In Case 1, there are (20 C 12) ways to choose the positions of the blue lights, with the remaining eight positions automatically assigned yellow. The expression "(20 C 12)" is the combination formula "20 choose 12," the number of ways choose 12 objects from a set of 20. This is (20!)/(12! x 8!) = 125970.
In Case 2, there are (20 C 11) ways to choose the positions of the blue lights, with the remaining nine positions automatically assigned yellow. There are (20 C 11) = 167960 ways to arrange them.
In Case 3, following the same logic, we have (20 C 10) = 184756.
Case 4 gives us (20 C 9) = 167960.
Case 5 gives us (20 C 8) = 125970.
Adding the results from the five different cases gives us a total of 772616 different ways to arrange blue and yellow light covers on the string of lights.
(6) Card Game Tournament Part 2 -- Hard
The eight friends of the previous problem want to conduct a round-robin bridge tournament, wherein every possible pair of players plays against every possible pair of opponents. How many different bridge games do they have to play to exhaust all possible matchups?
Solution: There are (8 C 2) = 28 ways to choose the first pair, and then (6 C 2) = 15 ways to choose the second pair they play against. If you multiply 28 and 15, you get 420, but this is an over-count by a factor of 2 since the order in which the pairs are chosen doesn't matter. So there are actually only 420/2 = 210 different matchups of pair-vs-pair in this tournament.
(7) Lights on a String Part 2 -- Challenging
Ava decides to use 10 blue and 10 yellow light covers. She also discovers that the ends of her string of lights are not distinguishable as she previously thought. This means that for Ava's purposes, a particular pattern and its reversal are completely equivalent. How many different patterns can she make?
Solution: In Problem 5 we found that there are 184756 ways to arrange 10 blue and 10 yellow light covers on a string of 20 lights with distinguishable ends. But if the ends are not distinguishable, then some of those 184756 patterns are duplicates.
We need to figure out how many of those 184756 patterns are duplicates. The patterns can be divided into two camps: those that look the same when the order of the light covers is reversed, and those that don't look the same. The patterns that don't look the same are the ones that get duplicated.
The easiest way to tackle this problem is to figure out how many patterns are in the first camp, the patterns that are the same forwards and backwards, the palindromes. In a palindrome pattern, the first 10 lights have an equal number of blue and yellow covers, i.e., five of each. There are (10 C 5) = 252 ways to choose the positions for the five blue light covers among the first 10 lights with the remaining five automatically assigned yellow. When we reverse this half-pattern and apply it to the last 10 lights on the string, we have created a palindromic pattern. Thus, there are 252 palindrome patterns.
The remaining 184756 - 252 = 184324 patterns are the duplicate pairs. Dividing this figure by 2 gives 92162 basic non-palindrome patterns. Thus, the total number of different patterns is 92162 + 252 = 92414.