Page 579 - Discrete Mathematics and Its Applications

558 8 / Advanced Counting Techniques

and data structures; 43 in both discrete mathematics and 20. How many elements are in the union of five sets if the
programming languages; and no student may take cal- sets contain 10,000 elements each, each pair of sets has
culus and discrete mathematics, or data structures and 1000 common elements, each triple of sets has 100 com-
programming languages, concurrently? mon elements, every four of the sets have 10 common
10. Find the number of positive integers not exceeding 100 elements, and there is 1 element in all five sets?
that are not divisible by 5 or by 7. 21. Write out the explicit formula given by the principle of
11. Find the number of positive integers not exceeding 100 inclusion–exclusion for the number of elements in the
that are either odd or the square of an integer. union of six sets when it is known that no three of these
sets have a common intersection.
12. Find the number of positive integers not exceeding 1000
that are either the square or the cube of an integer. ∗ 22. Prove the principle of inclusion–exclusion using mathe-
matical induction.
13. How many bit strings of length eight do not contain six
consecutive 0s? 23. Let E 1 , E 2 , and E 3 be three events from a sample space S.
∗ 14. How many permutations of the 26 letters of the English Find a formula for the probability of E 1 ∪ E 2 ∪ E 3 .
alphabet do not contain any of the strings fish, rat or bird? 24. Find the probability that when a fair coin is flipped five
15. How many permutations of the 10 digits either begin with times tails comes up exactly three times, the first and last
the 3 digits 987, contain the digits 45 in the fifth and sixth flips come up tails, or the second and fourth flips come
positions, or end with the 3 digits 123? up heads.
16. How many elements are in the union of four sets if 25. Find the probability that when four numbers from 1 to
each of the sets has 100 elements, each pair of the sets 100, inclusive, are picked at random with no repetitions
shares 50 elements, each three of the sets share 25 ele- allowed, either all are odd, all are divisible by 3, or all are
ments, and there are 5 elements in all four sets? divisible by 5.
17. How many elements are in the union of four sets if the 26. Find a formula for the probability of the union of four
sets have 50, 60, 70, and 80 elements, respectively, each events in a sample space if no three of them can occur at
pair of the sets has 5 elements in common, each triple of the same time.
the sets has 1 common element, and no element is in all 27. Find a formula for the probability of the union of five
four sets? events in a sample space if no four of them can occur at
18. How many terms are there in the formula for the number the same time.
of elements in the union of 10 sets given by the principle 28. Find a formula for the probability of the union of n events
of inclusion–exclusion? in a sample space when no two of these events can occur
19. Write out the explicit formula given by the principle of at the same time.
inclusion–exclusion for the number of elements in the 29. Find a formula for the probability of the union of n events
union of five sets. in a sample space.

8.6 Applications of Inclusion–Exclusion

Introduction

Many counting problems can be solved using the principle of inclusion–exclusion. For instance,
we can use this principle to find the number of primes less than a positive integer. Many problems
can be solved by counting the number of onto functions from one finite set to another. The
inclusion–exclusion principle can be used to find the number of such functions. The famous
hatcheck problem can be solved using the principle of inclusion–exclusion. This problem asks
for the probability that no person is given the correct hat back by a hatcheck person who gives
the hats back randomly.

An Alternative Form of Inclusion–Exclusion

There is an alternative form of the principle of inclusion–exclusion that is useful in counting
problems. In particular, this form can be used to solve problems that ask for the number of
elements in a set that have none of n properties P 1 ,P 2 ,...,P n .
Let A i be the subset containing the elements that have property P i . The number
).
P ...P i k
of elements with all the properties P i 1 ,P i 2 ,...,P i k will be denoted by N(P i 1 i 2