912 CHAPTER 13 Counting and Probability Look again at Example 1. A set with 3 elements has = 2 8 3 subsets. This result can be generalized. Analyzing Survey Data In a survey of 100 college students, 35 were registered in College Algebra, 52 were registered in Computer Science I, and 18 were registered in both courses. (a) How many students were registered in College Algebra or Computer Science I? (b) How many were registered in neither course? Solution EXAMPLE 2 (a) First, let = A set of students in College Algebra = B set of students in Computer Science I Then the given information tells us that ( ) ( ) ( ) = = ∩ = n A n B n A B 35 52 18 Refer to Figure 1. Since ( ) ∩ = n A B 18, the common part of the circles representing set A and set B has 18 elements. In addition, the remaining portion of the circle representing set A will have − = 35 18 17 elements. Similarly, the remaining portion of the circle representing set B has − = 52 18 34 elements. This means that + + = 17 18 34 69 students were registered in College Algebra or Computer Science I. (b) Since 100 students were surveyed, it follows that − = 100 69 31 were registered in neither course. Figure 1 Universal set A 18 34 31 17 B If A is a set with n elements, then A has 2n subsets. For example, the set { } a b c d e , , , , has = 2 32 5 subsets. Now Work PROBLEMS 17 AND 27 The solution to Example 2 contains the basis for a general counting formula. If we count the elements in each of two sets A and B, we necessarily count twice any elements that are in both A and B —that is, those elements in ∩A B. To count correctly the elements that are in A or B —that is, to find ( ) ∪ n A B —subtract those in ∩A B from ( ) ( ) + n A n B . THEOREM Counting Formula If A and B are finite sets, ( ) ( ) ( ) ( ) ∪ = + − ∩ nAB nA nB nAB (1) THEOREM Addition Principle of Counting If two sets A and B have no elements in common, that is, ( ) ( ) ( ) ∩ = ∅ ∪ = + A B n A B n A n B if , then (2) Refer to Example 2. Using formula (1), we have ( ) ( ) ( ) ( ) ∪ = + − ∩ = + − = nAB nA nB nAB 35 52 18 69 There are 69 students registered in College Algebra or Computer Science I. A special case of the Counting Formula (1) occurs if A and B have no elements in common. In this case, ∩ = ∅ A B , so ( ) ∩ = n A B 0. NOTE Recall in working with sets that the word or represents the union of sets. In this regard, the word or is inclusive. That is, if x is an element of ∪A B, then x can be in A or B or both. j
RkJQdWJsaXNoZXIy NjM5ODQ=