Page 435 - Discrete Mathematics and Its Applications

414 6 / Counting

21. How many permutations of the letters ABCDEFG con- 28. A professor writes 40 discrete mathematics true/false
tain questions. Of the statements in these questions, 17 are
a) the string BCD? true. If the questions can be positioned in any order, how
b) the string CFGA? many different answer keys are possible?
c) the strings BA and GF? ∗ 29. How many 4-permutations of the positive integers not ex-
d) the strings ABC and DE? ceeding 100 contain three consecutive integers k, k + 1,
e) the strings ABC and CDE? k + 2, in the correct order
f) the strings CBA and BED?
a) where these consecutive integers can perhaps be sep-
22. How many permutations of the letters ABCDEFGH con-
arated by other integers in the permutation?
tain
b) where they are in consecutive positions in the permu-
a) the string ED?
b) the string CDE? tation?
c) the strings BA and FGH? 30. Seven women and nine men are on the faculty in the
d) the strings AB, DE, and GH? mathematics department at a school.
e) the strings CAB and BED? a) How many ways are there to select a committee of
f) the strings BCA and ABF? five members of the department if at least one woman
23. How many ways are there for eight men and five women must be on the committee?
to stand in a line so that no two women stand next to each b) How many ways are there to select a committee of
other? [Hint: First position the men and then consider five members of the department if at least one woman
possible positions for the women.] and at least one man must be on the committee?
24. How many ways are there for 10 women and six men 31. The English alphabet contains 21 consonants and five
to stand in a line so that no two men stand next to each vowels. How many strings of six lowercase letters of the
other? [Hint: First position the women and then consider English alphabet contain
possible positions for the men.]
a) exactly one vowel?
25. One hundred tickets, numbered 1, 2, 3,..., 100, are sold b) exactly two vowels?
to100 differentpeoplefor adrawing.Fourdifferent prizes
areawarded,includingagrandprize(atriptoTahiti).How c) at least one vowel?
many ways are there to award the prizes if d) at least two vowels?
a) there are no restrictions? 32. How many strings of six lowercase letters from the En-
b) the person holding ticket 47 wins the grand prize? glish alphabet contain
c) the person holding ticket 47 wins one of the prizes? a) the letter a?
d) the person holding ticket 47 does not win a prize?
e) the people holding tickets 19 and 47 both win prizes? b) the letters a and b?
f) the people holding tickets 19, 47, and 73 all win c) the letters a and b in consecutive positions with a
prizes? preceding b, with all the letters distinct?
g) the people holding tickets 19, 47, 73, and 97 all win d) the letters a and b, where a is somewhere to the left
prizes? of b in the string, with all the letters distinct?
h) none of the people holding tickets 19, 47, 73, and 97
wins a prize? 33. Suppose that a department contains 10 men and 15
i) the grand prize winner is a person holding ticket 19, women. How many ways are there to form a commit-
tee with six members if it must have the same number of
47, 73, or 97?
j) the people holding tickets 19 and 47 win prizes, but men and women?
the people holding tickets 73and97 donotwinprizes? 34. Suppose that a department contains 10 men and 15
26. Thirteen people on a softball team show up for a game. women. How many ways are there to form a commit-
a) How many ways are there to choose 10 players to take tee with six members if it must have more women than
the field? men?
b) How many ways are there to assign the 10 positions 35. How many bit strings contain exactly eight 0s and 10 1s
by selecting players from the 13 people who show up? if every 0 must be immediately followed by a 1?
c) Of the 13 people who show up, three are women. How
many ways are there to choose 10 players to take the 36. How many bit strings contain exactly five 0s and 14 1s if
field if at least one of these players must be a woman? every 0 must be immediately followed by two 1s?
27. A club has 25 members. 37. How many bit strings of length 10 contain at least three
a) How many ways are there to choose four members of 1s and at least three 0s?
the club to serve on an executive committee? 38. How many ways are there to select 12 countries in the
b) How many ways are there to choose a president, vice United Nations to serve on a council if 3 are selected
president, secretary, and treasurer of the club, where from a block of 45, 4 are selected from a block of 57, and
no person can hold more than one office?
the others are selected from the remaining 69 countries?