Page 434 - Discrete Mathematics and Its Applications

6.3 Permutations and Combinations 413

EXAMPLE 14 How many bit strings of length n contain exactly r 1s?

Solution: The positions of r 1s in a bit string of length n form an r-combination of the set
{1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of length n that contain exactly r 1s. ▲

EXAMPLE 15 Suppose that there are 9 faculty members in the mathematics department and 11 in the computer
science department. How many ways are there to select a committee to develop a discrete
mathematics course at a school if the committee is to consist of three faculty members from the
mathematics department and four from the computer science department?
Solution: By the product rule, the answer is the product of the number of 3-combinations of
a set with nine elements and the number of 4-combinations of a set with 11 elements. By
Theorem 2, the number of ways to select the committee is

9! 11!
C(9, 3) · C(11, 4) = · = 84 · 330 = 27,720.
3!6! 4!7! ▲

Exercises

1. List all the permutations of {a, b, c}. 12. How many bit strings of length 12 contain
2. How many different permutations are there of the set a) exactly three 1s?
{a, b, c, d, e, f, g}? b) at most three 1s?
c) at least three 1s?
3. How many permutations of {a, b, c, d, e, f, g} end with
d) an equal number of 0s and 1s?
a?
13. A group contains n men and n women. How many ways
4. Let S ={1, 2, 3, 4, 5}.
are there to arrange these people in a row if the men and
a) List all the 3-permutations of S.
women alternate?
b) List all the 3-combinations of S.
14. In how many ways can a set of two positive integers less
5. Find the value of each of these quantities. than 100 be chosen?
a) P(6, 3) b) P(6, 5) 15. In how many ways can a set of five letters be selected
c) P(8, 1) d) P(8, 5) from the English alphabet?
e) P(8, 8) f) P(10, 9) 16. How many subsets with an odd number of elements does
6. Find the value of each of these quantities. a set with 10 elements have?
a) C(5, 1) b) C(5, 3) 17. How many subsets with more than two elements does a
c) C(8, 4) d) C(8, 8) set with 100 elements have?
e) C(8, 0) f) C(12, 6) 18. A coin is flipped eight times where each flip comes up
7. Find the number of 5-permutations of a set with nine el- either heads or tails. How many possible outcomes
ements. a) are there in total?
8. In how many different orders can five runners finish a b) contain exactly three heads?
c) contain at least three heads?
race if no ties are allowed?
d) contain the same number of heads and tails?
9. How many possibilities are there for the win, place, and
show (first, second, and third) positions in a horse race 19. A coin is flipped 10 times where each flip comes up either
with 12 horses if all orders of finish are possible? heads or tails. How many possible outcomes
a) are there in total?
10. There are six different candidates for governor of a state. b) contain exactly two heads?
In how many different orders can the names of the can- c) contain at most three tails?
didates be printed on a ballot?
d) contain the same number of heads and tails?
11. How many bit strings of length 10 contain
20. How many bit strings of length 10 have
a) exactly four 1s?
a) exactly three 0s?
b) at most four 1s? b) more 0s than 1s?
c) at least four 1s? c) at least seven 1s?
d) an equal number of 0s and 1s? d) at least three 1s?