Page 463 - Discrete Mathematics and Its Applications

442 6 / Counting

24. Show that if n and r are nonnegative integers and n ≥ r, in every subset A i there are elements that have been
then assigned each color. Let m(d) be the largest integer such
P(n + 1,r) = P(n, r)(n + 1)/(n + 1 − r). that every collection of fewer than m(d) sets each con-
taining d elements is 2-colorable.
∗ 25. SupposethatS isasetwithnelements.Howmanyordered
pairs (A, B) are there such that A and B are subsets of S a) Show that the collection of all subsets with d elements
of a set S with 2d − 1 elements is not 2-colorable.
with A ⊆ B?[Hint: Show that each element of S belongs
to A, B − A,or S − B.] b) Show that m(2) = 3.
∗∗ c) Show that m(3) = 7. [Hint: Show that the collec-
26. Give a combinatorial proof of Corollary 2 of Section 6.4 tion {1, 3, 5}, {1, 2, 6}, {1, 4, 7}, {2, 3, 4}, {2, 5, 7},
by setting up a correspondence between the subsets of a {3, 6, 7}, {4, 5, 6} is not 2-colorable. Then show that
set with an even number of elements and the subsets of all collections of six sets with three elements each are
this set with an odd number of elements. [Hint:Take an el- 2-colorable.]
ement a in the set. Set up the correspondence by putting a
in the subset if it is not already in it and taking it out if it 35. A professor writes 20 multiple-choice questions, each
is in the subset.] with the possible answer a, b, c,or d, for a discrete
mathematics test. If the number of questions with a, b, c,
27. Let n and r be integers with 1 ≤ r< n. Show that and d as their answer is 8, 3, 4, and 5, respectively, how
many different answer keys are possible, if the questions
C(n, r − 1) = C(n + 2,r + 1)
can be placed in any order?
− 2C(n + 1,r + 1) + C(n, r + 1).
36. How many different arrangements are there of eight peo-
n ple seated at a round table, where two arrangements are
28. Proveusingmathematicalinductionthat j = 2 C(j, 2) =
C(n + 1, 3) whenever n is an integer greater than 1. considered the same if one can be obtained from the other
by a rotation?
29. Show that if n is an integer then
37. How many ways are there to assign 24 students to five
n
k n n faculty advisors?
3 = 4 .
k 38. How many ways are there to choose a dozen apples from a
k = 0
bushel containing 20 indistinguishable Delicious apples,
n
n−1 n
30. Show that 1 = if n is an integer with 20 indistinguishable Macintosh apples, and 20 indistin-
i=1 j=i+1 2
n ≥ 2. guishable Granny Smith apples, if at least three of each
n
n−2 n−1 n kind must be chosen?
31. Show that 1 = if n is an in-
i=1 j=i+1 k=j+1 3
teger with n ≥ 3. 39. How many solutions are there to the equation x 1 + x 2 +
x 3 = 17, where x 1 , x 2 , and x 3 are nonnegative integers
32. In this exercise we will derive a formula for the sum of with
the squares of the n smallest positive integers. We will a) x 1 > 1, x 2 > 2, and x 3 > 3?
count the number of triples (i,j,k) where i, j, and k are
integers such that 0 ≤ i< k,0 ≤ j< k, and 1 ≤ k ≤ n b) x 1 < 6 and x 3 > 5?
in two ways. c) x 1 < 4, x 2 < 3, and x 3 > 5?
2
a) Show that there are k such triples with a fixed k. De- 40. a) Howmanydifferentstringscanbemadefromtheword
n 2 PEPPERCORN when all the letters are used?
duce that there are k such triples.
k = 1
b) How many of these strings start and end with the
b) Show that the number of such triples with letter P?
0 ≤ i< j < k and the number of such triples with
0 ≤ j< i < k both equal C(n + 1, 3). c) In how many of these strings are the three letter Ps
consecutive?
c) Show that the number of such triples with 0 ≤ i =
41. How many subsets of a set with ten elements
j< k equals C(n + 1, 2).
a) have fewer than five elements?
d) Combining part (a) with parts (b) and (c), conclude b) have more than seven elements?
that
n c) have an odd number of elements?
2
k = 2C(n + 1, 3) + C(n + 1, 2) 42. A witness to a hit-and-run accident tells the police that
the license plate of the car in the accident, which contains
k = 1
= n(n + 1)(2n + 1)/6. three letters followed by three digits, starts with the let-
ters AS and contains both the digits 1 and 2. How many
∗ 33. How many bit strings of length n, where n ≥ 4, contain different license plates can fit this description?
exactly two occurrences of 01? 43. How many ways are there to put n identical objects into
34. Let S be a set. We say that a collection of sub- m distinct containers so that no container is empty?
sets A 1 ,A 2 ,...,A n each containing d elements, where 44. How many ways are there to seat six boys and eight girls
d ≥ 2, is 2-colorable if it is possible to assign to in a row of chairs so that no two boys are seated next to
each element of S one of two different colors so that each other?