Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.5—Generalized Permutations and Combinations
p.373, icon at Example 4
#1. A jar contains 30 pennies, 20 nickels, 20 dimes, and 15 quarters. (The coins of each denomination are considered to be identical.)
(a) Find the number of ways to put all 85 coins in a row.
(b) Find the number of possible handfuls of 12 coins.
Solution:
(a) The answer is not 85! because not all the coins are distinct. Think of the problem as one of taking 30 p’s, 20 n’s, 20 d’s, and 15 q’s, and putting these letters in a row. Taking into account the identical letters,
we have 85! / 30! · 20! · 20! · 15! .
(b) The number of handfuls of 12 coins is equal to the number of nonnegative integer solutions to the equation p + n + d + q = 12.
The number of solutions to this equation is C(15, 3) = 455.
Solution:
(a) Each book can be placed in any of the four boxes. By the product rule, this can be done in 410 ways.
(b) Let xi be the number of books in box i. We need to find the number of nonnegative integer solutions to the equation x1 + x2 + x3 + x4 = 10. There are C(13, 3) such solutions.
Extra Examples
Section 5.5—Generalized Permutations and Combinations
p.373, icon at Example 4
#1. A jar contains 30 pennies, 20 nickels, 20 dimes, and 15 quarters. (The coins of each denomination are considered to be identical.)
(a) Find the number of ways to put all 85 coins in a row.
(b) Find the number of possible handfuls of 12 coins.
Solution:
(a) The answer is not 85! because not all the coins are distinct. Think of the problem as one of taking 30 p’s, 20 n’s, 20 d’s, and 15 q’s, and putting these letters in a row. Taking into account the identical letters,
we have 85! / 30! · 20! · 20! · 15! .
(b) The number of handfuls of 12 coins is equal to the number of nonnegative integer solutions to the equation p + n + d + q = 12.
The number of solutions to this equation is C(15, 3) = 455.
p.373, icon at Example 4
#2. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose:
(a) at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) exactly 3 chocolate cookies and exactly 6 peanut butter cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
(a) We must have c ≥ 3 and p ≥ 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies into the bag. You have met the two conditions, so you do not care about the numbers of each of the four types you choose for the remaining 21 cookies.
Therefore, you need to find the number of nonnegative integer solutions to the equation c + j + s + p = 21.
The number of nonnegative integer solutions to this equation is C(24, 3). Therefore there are C(24, 3) = 2,024 ways to buy 30 cookies with at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) We must have c = 3 and p = 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies in to the bag, but you cannot select more chocolate or peanut butter cookies. Therefore you need to find the number of nonnegative integer solutions to the equation j + s = 21.
The number of nonnegative integer solutions to this equation is C(22, 1) = 22. Therefore there are 22 ways to buy 30 cookies with exactly 3 chocolate cookies and exactly 6 peanut butter cookies.
p.373, icon at Example 4
#3. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at most 5 sugar cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
To solve the problem, we use “complement counting”. That is, we find the number of possible bags of 30 cookies with more than 5 sugar cookies, and then subtract that number from the total number of bags of 30 cookies. That is, we find the number of solutions to c + j + s + p = 30 with s ≥ 6. This is the number of solutions to the equation c + j + s + p = 24, which equals C(27, 3).
Thus, the answer to the question is the total number of nonnegative integer solutions to the equation c + j + s + p = 30, C(33, 3), with C(27, 3) subtracted: (total number of solutions) − (number of solutions with s ≥ 6) = C(33, 3) − C(27, 3) = 2,531.
#2. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose:
(a) at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) exactly 3 chocolate cookies and exactly 6 peanut butter cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
(a) We must have c ≥ 3 and p ≥ 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies into the bag. You have met the two conditions, so you do not care about the numbers of each of the four types you choose for the remaining 21 cookies.
Therefore, you need to find the number of nonnegative integer solutions to the equation c + j + s + p = 21.
The number of nonnegative integer solutions to this equation is C(24, 3). Therefore there are C(24, 3) = 2,024 ways to buy 30 cookies with at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) We must have c = 3 and p = 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies in to the bag, but you cannot select more chocolate or peanut butter cookies. Therefore you need to find the number of nonnegative integer solutions to the equation j + s = 21.
The number of nonnegative integer solutions to this equation is C(22, 1) = 22. Therefore there are 22 ways to buy 30 cookies with exactly 3 chocolate cookies and exactly 6 peanut butter cookies.
p.373, icon at Example 4
#3. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at most 5 sugar cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
To solve the problem, we use “complement counting”. That is, we find the number of possible bags of 30 cookies with more than 5 sugar cookies, and then subtract that number from the total number of bags of 30 cookies. That is, we find the number of solutions to c + j + s + p = 30 with s ≥ 6. This is the number of solutions to the equation c + j + s + p = 24, which equals C(27, 3).
Thus, the answer to the question is the total number of nonnegative integer solutions to the equation c + j + s + p = 30, C(33, 3), with C(27, 3) subtracted: (total number of solutions) − (number of solutions with s ≥ 6) = C(33, 3) − C(27, 3) = 2,531.
p.373, icon at Example 4
#4. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at least one of each of the four types of cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
To “see” the solution, take an empty bag and place in it one cookie of each of the four types. This leaves 26 more cookies to be selected and there are no additional restrictions on the cookies. This yields the equation c + j + s + p = 26. The number of nonnegative integer solutions to this new equation is C(29, 3) = 3,654.
p.375, icon at Example 7
#1. In how many ways can the letters in DECEIVED be arranged in a row?
Solution:
The word has two D’s, three E’s, one C, one I, and one V. Therefore, the number of permutations of DECEIVED is 8! / (2! · 3! · 1! · 1! · 1!) = 8! /( 2! · 3!) = 3,360.
p.375, icon at Example 7
#2. In how many ways can 7 of the 8 letters in CHEMISTS be put in a row?
#4. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at least one of each of the four types of cookies.
Solution:
We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.
To “see” the solution, take an empty bag and place in it one cookie of each of the four types. This leaves 26 more cookies to be selected and there are no additional restrictions on the cookies. This yields the equation c + j + s + p = 26. The number of nonnegative integer solutions to this new equation is C(29, 3) = 3,654.
p.375, icon at Example 7
#1. In how many ways can the letters in DECEIVED be arranged in a row?
Solution:
The word has two D’s, three E’s, one C, one I, and one V. Therefore, the number of permutations of DECEIVED is 8! / (2! · 3! · 1! · 1! · 1!) = 8! /( 2! · 3!) = 3,360.
p.375, icon at Example 7
#2. In how many ways can 7 of the 8 letters in CHEMISTS be put in a row?
Solution:
There are two patterns to consider:
(a) seven distinct letters are selected (that is, only one S is selected), and
(b) the two S’s are selected.
In the first pattern, there are 7! ways to put the 7 distinct letters in a row.
In the second pattern, we select the two S’s and use all but one of the six other letters. For example, we could use the letters S,S and C,H,E,M,T, or S,S and C,H,E,M,I. Each of these sets of seven letters can be put in a row in 7!/2 ways. There are 6 ways to choose five of the six letters that are not S’s; therefore, there are 6 · 7!/2 ways to have the second pattern.
Adding the totals obtained from the two cases, we have the total number of ways to put seven of the eight letters in a row is 7! + 6 · (7!/2!) = 20,160.
There are two patterns to consider:
(a) seven distinct letters are selected (that is, only one S is selected), and
(b) the two S’s are selected.
In the first pattern, there are 7! ways to put the 7 distinct letters in a row.
In the second pattern, we select the two S’s and use all but one of the six other letters. For example, we could use the letters S,S and C,H,E,M,T, or S,S and C,H,E,M,I. Each of these sets of seven letters can be put in a row in 7!/2 ways. There are 6 ways to choose five of the six letters that are not S’s; therefore, there are 6 · 7!/2 ways to have the second pattern.
Adding the totals obtained from the two cases, we have the total number of ways to put seven of the eight letters in a row is 7! + 6 · (7!/2!) = 20,160.
p.376, icon after start of ”Distributing Objects into Boxes” subsection
#1. Four players are playing bridge. In how many ways can they be dealt hands of cards? (In bridge, a hand of cards consists of 13 out of 52 cards.)
Solution:
This is a problem of placing 52 distinguishable objects (the cards) in four distinguishable piles of size 13 (one pile for each of the four players). This can be done is 52! / 13!·13!·13!·13! ways.
#1. Four players are playing bridge. In how many ways can they be dealt hands of cards? (In bridge, a hand of cards consists of 13 out of 52 cards.)
Solution:
This is a problem of placing 52 distinguishable objects (the cards) in four distinguishable piles of size 13 (one pile for each of the four players). This can be done is 52! / 13!·13!·13!·13! ways.
p.376, icon after start of ”Distributing Objects into Boxes” subsection
#2. In how many ways can ten books be put in four labeled boxes, if one or more of the boxes can be empty? Assume that the books are:
(a) distinct.
(b) identical.
#2. In how many ways can ten books be put in four labeled boxes, if one or more of the boxes can be empty? Assume that the books are:
(a) distinct.
(b) identical.
Solution:
(a) Each book can be placed in any of the four boxes. By the product rule, this can be done in 410 ways.
(b) Let xi be the number of books in box i. We need to find the number of nonnegative integer solutions to the equation x1 + x2 + x3 + x4 = 10. There are C(13, 3) such solutions.
No comments:
Post a Comment