Page 418 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 397

25. How many strings of three decimal digits 35. How many one-to-one functions are there from a set with
a) do not contain the same digit three times? five elements to sets with the following number of ele-
b) begin with an odd digit? ments?
c) have exactly two digits that are 4s? a) 4 b) 5 c) 6 d) 7
26. How many strings of four decimal digits 36. How many functions are there from the set {1, 2,...,n},
a) do not contain the same digit twice? where n is a positive integer, to the set {0, 1}?
b) end with an even digit? 37. How many functions are there from the set {1, 2, ...,n},
c) have exactly three digits that are 9s? where n is a positive integer, to the set {0, 1}
27. A committee is formed consisting of one representative a) that are one-to-one?
from each of the 50 states in the United States, where the b) that assign 0 to both 1 and n?
representative from a state is either the governor or one c) that assign 1 to exactly one of the positive integers
of the two senators from that state. How many ways are less than n?
there to form this committee? 38. How many partial functions (see Section 2.3) are there
28. How many license plates can be made using either three from a set with five elements to sets with each of these
digits followed by three uppercase English letters or three number of elements?
uppercase English letters followed by three digits? a) 1 b) 2 c) 5 d) 9
29. How many license plates can be made using either two 39. How many partial functions (see Definition 13 of Section
uppercase English letters followed by four digits or two 2.3) are there from a set with m elements to a set with n
digits followed by four uppercase English letters? elements, where m and n are positive integers?
30. How many license plates can be made using either three 40. How many subsets of a set with 100 elements have more
uppercase English letters followed by three digits or four than one element?
uppercase English letters followed by two digits? 41. A palindrome is a string whose reversal is identical to the
31. How many license plates can be made using either two string. How many bit strings of length n are palindromes?
or three uppercase English letters followed by either two 42. How many 4-element DNA sequences
or three digits? a) do not contain the base T?
32. How many strings of eight uppercase English letters are b) contain the sequence ACG?
there c) contain all four bases A, T, C, and G?
a) if letters can be repeated? d) contain exactly three of the four basesA, T, C, and G?
b) if no letter can be repeated? 43. How many 4-element RNA sequences
c) that start with X, if letters can be repeated? a) contain the base U?
d) that start with X, if no letter can be repeated? b) do not contain the sequence CUG?
e) that start and end with X, if letters can be repeated? c) do not contain all four bases A, U, C, and G?
f) that start with the letters BO (in that order), if letters d) contain exactly two of the four bases A, U, C, and G?
can be repeated? 44. How many ways are there to seat four of a group of ten
g) that start and end with the letters BO (in that order), people around a circular table where two seatings are con-
if letters can be repeated? sidered the same when everyone has the same immediate
h) that start or end with the letters BO (in that order), if left and immediate right neighbor?
letters can be repeated? 45. How many ways are there to seat six people around a cir-
33. How many strings of eight English letters are there cular table where two seatings are considered the same
a) that contain no vowels, if letters can be repeated? when everyone has the same two neighbors without re-
b) that contain no vowels, if letters cannot be repeated? gard to whether they are right or left neighbors?
c) that start with a vowel, if letters can be repeated? 46. In how many ways can a photographer at a wedding ar-
d) that start with a vowel, if letters cannot be repeated? range 6 people in a row from a group of 10 people, where
e) that contain at least one vowel, if letters can be re- the bride and the groom are among these 10 people, if
peated? a) the bride must be in the picture?
f) that contain exactly one vowel, if letters can be re- b) both the bride and groom must be in the picture?
peated? c) exactly one of the bride and the groom is in the pic-
g) that start with X and contain at least one vowel, if ture?
letters can be repeated? 47. In how many ways can a photographer at a wedding ar-
h) that start and end with X and contain at least one range six people in a row, including the bride and groom,
vowel, if letters can be repeated? if
34. How many different functions are there from a set with a) the bride must be next to the groom?
10 elements to sets with the following numbers of ele- b) the bride is not next to the groom?
ments? c) the bride is positioned somewhere to the left of the
a) 2 b) 3 c) 4 d) 5 groom?