Chapter ObjeCtives
After studying this chapter, you will be able to:
• Use the notation of set theory.
• Find the power set of a finite set.
• Find the union, intersection, difference, complement, and Cartesian product
of sets.
• Identify binary and unary operations on a set.
• Prove set identities.
• Recognize that not all sets are countable.
• Apply the multiplication principle and the addition principle to solve counting
problems.
• Use decision trees to solve counting problems.
• Use the principle of inclusion and exclusion to find the number of elements in
the union of sets.
• Use the pigeonhole principle to decide when certain events must occur.
• Use the formulas for permutations and combinations of r objects, with and
without repetition, from a set of n distinct objects.
• Find the number of distinct permutations of n objects that are not all distinct.
• Generate all permutations of n distinct objects, and all combinations of r out
of n distinct objects.
• Find the probability of an event given that all outcomes are equally likely, that
a probability distribution has been assigned to the outcomes, or that another
event has already occurred.
• Compute the expected value of a quantity with an assigned probability
distribution.
• Use the binomial theorem to expand (a + b)
n
.
You survey the 87 computer users who subscribe to your electronic newsletter in
preparation for the release of your new software product. The results of your survey
reveal that 68 have a Windows-based system available to them, 34 have a Linux
system available, and 30 have access to a Mac. In addition, 19 have access to both
Windows and Linux systems, 11 have access to both Linux systems and Macs, and
23 can use both Macs and Windows.
Question: How many of your subscribers have access to all three types of systems?
4 4
Sets, Combinatorics,
and Probability
C h a p t e r
221
After studying this chapter, you will be able to:
• Use the notation of set theory.
• Find the power set of a finite set.
• Find the union, intersection, difference, complement, and Cartesian product
of sets.
• Identify binary and unary operations on a set.
• Prove set identities.
• Recognize that not all sets are countable.
• Apply the multiplication principle and the addition principle to solve counting
problems.
• Use decision trees to solve counting problems.
• Use the principle of inclusion and exclusion to find the number of elements in
the union of sets.
• Use the pigeonhole principle to decide when certain events must occur.
• Use the formulas for permutations and combinations of r objects, with and
without repetition, from a set of n distinct objects.
• Find the number of distinct permutations of n objects that are not all distinct.
• Generate all permutations of n distinct objects, and all combinations of r out
of n distinct objects.
• Find the probability of an event given that all outcomes are equally likely, that
a probability distribution has been assigned to the outcomes, or that another
event has already occurred.
• Compute the expected value of a quantity with an assigned probability
distribution.
• Use the binomial theorem to expand (a + b)
n
.
You survey the 87 computer users who subscribe to your electronic newsletter in
preparation for the release of your new software product. The results of your survey
reveal that 68 have a Windows-based system available to them, 34 have a Linux
system available, and 30 have access to a Mac. In addition, 19 have access to both
Windows and Linux systems, 11 have access to both Linux systems and Macs, and
23 can use both Macs and Windows.
Question: How many of your subscribers have access to all three types of systems?
4 4
Sets, Combinatorics,
and Probability
C h a p t e r
221