Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.3—Permutations and Combinations
p.355, icon at Example 1
#1. A class has 30 students enrolled. In how many ways can:
(a) four be put in a row for a picture?
(b) all 30 be put in a row for a picture?
(c) all 30 be put in two rows of 15 each (that is, a front row and a back row) for a picture?
Solution:
(a) We need to fill in the following row of four blanks: . This can be done in 30 · 29 · 28 · 27 ways.
This is the number of 4-permutations from a set of 30, which is P(30, 4).
(b) The answer can be visualized as the number of ways to fill in a row of 30 blanks with the 30 students,
which is 30!, or P(30, 30).
(c) The answer can be visualized as the number of ways to fill in two rows, each with 15 blanks, with the 30 students:
We can begin by filling in the bottom row, which can be done in 30 · 29 · 28 · . . . · 17 · 16 ways. Then we fill in the top row, which can be done in 15 · 14 · 13 · . . . · 2 · 1 ways. Therefore the answer is (30 · 29 · 28 · · · 17 · 16) · (15 · 14 · 13 · · · 2 · 1) = 30 ! .
p.355, icon at Example 1
#2. A class has 20 women and 16 men. In how many ways can you
(a) put all the students in a row?
(b) put 7 of the students in a row?
(c) put all the students in a row if all the women are on the left and all the men are on the right?
Solution:
(a) There are 36 students. They can be put in a row in 36! ways.
(b) You need to have an ordered arrangement of 7 out of 36 students. The number of such arrangements is P(36, 7).
(c) You need to have an ordered arrangement of all 20 women AND and ordered arrangement of all 16 men.
By the product rule, this can be done in 20!·16! ways.
p.360, icon at Example 12
#1. A certain type of push-button door lock requires you to enter a code before the lock will open. The lock has five buttons, numbered 1, 2, 3, 4, 5. The lock is programmed to recognize six different 4-digit codes, with repeated digits allowed in each code. How many different sets of recognizable codes are there?
Solution:
There are 5^4 = 625 possible four-digit codes. Therefore, there are C(625, 6) different sets of six codes that the lock can be programmed to recognize.
p.360, icon at Example 12
#2. Several states play a lottery game called Mega Millions. On a Mega Millions lottery game ticket, you pick a set of five numbers from the numbers 1 through 56 on the top panel of the ticket, and one number (the Mega Ball number) from 1 through 46 on the bottom half of the ticket. (The Mega Ball number can be the same as one of the five numbers picked on the top half of the ticket.) A set of six winning numbers is selected: five numbers from 1 through 56 and one Mega Ball number from the numbers 1 through 46. You win a prize if your selections match some or all of the winning numbers, as follows: five and Mega Ball, five and no Mega Ball, four and Mega Ball, four and no Mega Ball, three and Mega Ball, three and no Mega Ball, two and Mega Ball, one and Mega Ball, only the Mega Ball.
Find the number of ways in which you can have one ticket with
(a) five winning numbers, but no Mega Ball.
(b) two winning numbers and the Mega Ball.
Solution:
(a) The number of ways in which all five numbers can be chosen correctly is C(5, 5) = 1 and the number of ways of choosing a number other than the Mega Ball is C(45, 1) = 45. Therefore, the number of ways to choose five numbers and miss the Mega Ball is C(5, 5)· C(45, 1) = 45.
(b) The number of ways in which exactly two of the five numbers can be chosen correctly is C(5, 2)· C(51, 3) — you choose two of the five winning numbers and three of the 51 losing numbers. The number of ways of choosing the Mega Ball is C(1, 1). Therefore, the number of ways to choose exactly two winning numbers and the Mega Ball is C(5, 2)· C(51, 3)· C(1, 1) = 208, 250.
p.360, icon at Example 12
#3. How many ways are there to choose a committee of size five consisting of three women and two men from a group of ten women and seven men?
Solution:
The number of ways to choose three women is C(10, 3) and the number of ways to choose two men is C(7, 2). Using the product rule to choose three women and two men, the answer is C(10, 3) · C(7, 2) = 2, 520.
Note: The answer is not C(17, 5) (which counts all committees of size five) because this ignores that fact that the committees must have exactly three women and exactly two men. Also, the answer is not C(10, 3) + C(7, 2), which is a commonly made mistake. This says that you are choosing either three women or two 2men; it does not count committees of size five.
p.360, icon at Example 12
#4. Let S = {1, 2, . . . , 19}. Find the number of subsets of S with equal numbers of odd integers and even integers.
Solution:
Note that there are 10 odd integers and 9 even integers in S. The subsets to be counted must consist of k odd integers and k even integers, where k = 1, 2, 3, . . . , 9. Therefore, by the product rule, the number of each type is C(10, k)· C(9, k). Therefore, by the sum rule the answer is
C(10, 0) · C(9, 0) subsets with 0 odd and 0 even + C(10, 1)· C(9, 1) subsets with 1 odd and 1 even + C(10, 2)· C(9, 2)m subsets with 2 odd and 2 even + · · · + C(10, 9)· C(9, 9) subsets with 9 odd and 9 even = 92,377.
or
C(10, 0) · C(9, 0) + C(10, 1)· C(9, 1) + C(10, 2)· C(9, 2) + · · · + C(10, 9)· C(9, 9) = 92,377.
p.360, icon at Example 12
#5. Find the number of words of length 10 of letters of the alphabet, with no repeated letters, such that each word has equal numbers of vowels and consonants.
Solution:
Visualize a row of ten blanks. Each word of length 10 must contain all five vowels and five of the 21 consonants. There are different ways to solve this problem.
Here is one way to solve the problem. Choose a set of five of the ten blanks for the vowels. Then place the five vowels in these positions. These two steps can be done in C(10, 5)· 5! ways. Next, choose 5 consonants from the 21 consonants, and place them in the remaining five blanks. These two steps can be done in C(21, 5)· 5! ways. Thus, the number of ways of forming the desired words by placing the vowels and consonants is C(10, 5)·5!·C(21, 5)·5! = (10!/5!5!)·5!·(21!/5!16!)·5! =10!21!5!16!= 10·9·8·7·6·21·20·19·18·17 = 73,842,451,200.
Here is a second way to approach the problem. Choose any set of five consonants, and form a set consisting of these five consonants and the five vowels. These ten letters can be arranged in 10! ways, each of which forms one of the words we are counting. But there are C(21, 5) ways to choose the five consonants. Therefore, there are C(21, 5) · 10! = 10·9·8·7·6 · 21·20·19·18·17 words.
Here is a third way to approach the problem. First, place the five vowels in five of the ten blanks (10 choices for A, 9 choices for E, etc.) — this can be done in 10·9·8·7·6 ways. Then place five of the 21 consonants in the five remaining blanks (21 choices for the first blank, 20 choices for the second blank, etc.) — this can be done in 21·20·19·18·17 ways. Therefore, by the product rule, the number of words with the five vowels and five consonants is 10·9·8·7·6 · 21·20·19·18·17.
p.360, icon at Example 12
#6. Find the number of ways to take an ordinary deck of 52 playing cards and break it into:
(a) four equal piles, labeled A, B, C, D.
(b) four equal piles that are not labeled.
Solution:
(a) Each pile must have 52/4 = 13 cards in it. In sequence, we form pile A, then pile B, then pile C, and finally pile D. There are C(52, 13) ways to obtain pile A, C(39, 13) ways to obtain pile B, C(26, 13) ways to obtain pile C, and C(13, 13) = 1 way to obtain pile D. Therefore, by the product rule the answer is
C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13) = (52!/13! · 39!)·(39!/13! · 26!)·(26!/13! · 13!)·(13!/13! · 0!) = 52!/(13!)^4.
(b) If the four piles are not labeled, there is no distinction to be made among piles A, B, C, D. We can permute these in 4! ways. Hence the answer is the answer to part (a) divided by 4!:
(C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13))/4! = 52! / ((13!)^4)· 4!).
p.360, icon at Example 12
#7. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of two odd numbers and three even numbers.
Solution:
There are 13 odd numbers; we can choose two in C(13, 2) ways. There are 12 even numbers; we can choose three in C(12, 3) ways. Using the product rule to find the number of elements in T , we have C(13, 2) · C(12, 3) =17,160 subsets.
p.360, icon at Example 12
#8. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of exactly three prime numbers.
Solution:
(b) The prime numbers in S are 2, 3, 5, 7, 11, 13, 17, 19, and 23, and there are C(9, 3) ways to select three
of them. But we also need to select two of the 16 composite numbers to make T have size five; there are C(16, 2) ways to this. Therefore, the product rule gives C(9, 3) · C(16, 2) = 10,080 possible subsets T .
p.360, icon at Example 12
#9. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has the sum of its elements less than 18.
Solution:
There are very few subsets with this property. It is easiest in this case to count directly the set of five numbers whose sum is less than 18: 1, 2, 3, 4, 5, 1, 2, 3, 4, 6, 1, 2, 3, 4, 7, 1, 2, 3, 5, 6. Thus, there are four such subsets.
p.360, icon at Example 12
#10. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has at least one even number in it.
Solution:
It is easiest to count the total number of subsets of size five, and then subtract the number of subsets with no even numbers in them: C(25, 5) − C(13, 5) = 51,843.
Note: When you need to count objects that have a certain property, a good problem solving strategy to consider is “complement counting” — count the total number of objects in the universe and then subtract the number of objects that fail to have the desired property.
