Page 453 - Discrete Mathematics and Its Applications

432 6 / Counting

Exercises

1. In how many different ways can five elements be selected 12. How many different combinations of pennies, nickels,
in order from a set with three elements when repetition is dimes, quarters, and half dollars can a piggy bank con-
allowed? tain if it has 20 coins in it?
2. In how many different ways can five elements be selected 13. A book publisher has 3000 copies of a discrete mathemat-
in order from a set with five elements when repetition is ics book. How many ways are there to store these books
allowed? in their three warehouses if the copies of the book are
indistinguishable?
3. How many strings of six letters are there?
14. How many solutions are there to the equation
4. Every day a student randomly chooses a sandwich for
lunch from a pile of wrapped sandwiches. If there are six x 1 + x 2 + x 3 + x 4 = 17,
kinds of sandwiches, how many different ways are there where x 1 ,x 2 ,x 3 , and x 4 are nonnegative integers?
for the student to choose sandwiches for the seven days 15. How many solutions are there to the equation
of a week if the order in which the sandwiches are chosen
matters? x 1 + x 2 + x 3 + x 4 + x 5 = 21,
5. How many ways are there to assign three jobs to five where x i , i = 1, 2, 3, 4, 5, is a nonnegative integer such
employees if each employee can be given more than one that
job? a) x 1 ≥ 1?
6. How many ways are there to select five unordered ele- b) x i ≥ 2 for i = 1, 2, 3, 4, 5?
ments from a set with three elements when repetition is c) 0 ≤ x 1 ≤ 10?
allowed? d) 0 ≤ x 1 ≤ 3, 1 ≤ x 2 < 4, and x 3 ≥ 15?
16. How many solutions are there to the equation
7. How many ways are there to select three unordered el-
ements from a set with five elements when repetition is x 1 + x 2 + x 3 + x 4 + x 5 + x 6 = 29,
allowed?
wherex i ,i = 1, 2, 3, 4, 5, 6,isanonnegativeintegersuch
8. How many different ways are there to choose a dozen that
donuts from the 21 varieties at a donut shop?
a) x i > 1 for i = 1, 2, 3, 4, 5, 6?
9. A bagel shop has onion bagels, poppy seed bagels, egg b) x 1 ≥ 1, x 2 ≥ 2, x 3 ≥ 3, x 4 ≥ 4, x 5 > 5, and x 6 ≥ 6?
bagels, salty bagels, pumpernickel bagels, sesame seed c) x 1 ≤ 5?
bagels, raisin bagels, and plain bagels. How many ways d) x 1 < 8 and x 2 > 8?
are there to choose 17. How many strings of 10 ternary digits (0, 1, or 2) are there
a) six bagels? that contain exactly two 0s, three 1s, and five 2s?
b) a dozen bagels? 18. How many strings of 20-decimal digits are there that con-
tain two 0s, four 1s, three 2s, one 3, two 4s, three 5s, two
c) two dozen bagels?
7s, and three 9s?
d) a dozen bagels with at least one of each kind?
19. Suppose that a large family has 14 children, including two
e) a dozen bagels with at least three egg bagels and no
sets of identical triplets, three sets of identical twins, and
more than two salty bagels?
two individual children. How many ways are there to seat
10. A croissant shop has plain croissants, cherry croissants,
these children in a row of chairs if the identical triplets or
chocolate croissants, almond croissants, apple croissants, twins cannot be distinguished from one another?
and broccoli croissants. How many ways are there to
choose 20. How many solutions are there to the inequality
a) a dozen croissants? x 1 + x 2 + x 3 ≤ 11,
b) three dozen croissants? where x 1 , x 2 , and x 3 are nonnegative integers? [Hint: In-
c) two dozen croissants with at least two of each kind? troduce an auxiliary variable x 4 such that x 1 + x 2 + x 3 +
d) two dozen croissants with no more than two broccoli x 4 = 11.]
croissants? 21. How many ways are there to distribute six indistinguish-
e) two dozen croissants with at least five chocolate crois- able balls into nine distinguishable bins?
sants and at least three almond croissants? 22. How many ways are there to distribute 12 indistinguish-
f) two dozen croissants with at least one plain croissant, able balls into six distinguishable bins?
at least two cherry croissants, at least three choco- 23. How many ways are there to distribute 12 distinguishable
late croissants, at least one almond croissant, at least objects into six distinguishable boxes so that two objects
two apple croissants, and no more than three broccoli are placed in each box?
croissants? 24. How many ways are there to distribute 15 distinguish-
11. How many ways are there to choose eight coins from a able objects into five distinguishable boxes so that the
piggy bank containing 100 identical pennies and 80 iden- boxes have one, two, three, four, and five objects in them,
tical nickels? respectively.