example for the inclusion and exclusion principal
Answers
Answer:
A good understanding of the inclusion-exclusion principle in Discrete Mathematics is vital for building a solid foundation in set theory. With the inclusion-exclusion principle, there are generally two types of questions that appear in introductory and lower level Discrete Mathematics syllabi. In this article, we will discuss several inclusion-exclusion principle examples and solutions for both question types. Venn diagrams, although not essential, are useful in conceptualizing these types of questions. The two question types are:
The number of elements in certain sets are given as well as how many live in certain set intersections. It is then necessary to determine – to the exclusion of other sets – the number of elements living in a certain set or subset. (Hence, the ‘exclusion’ part of this principle.)
The second type is more complex. The number of elements living in the intersection of sets are unknown and need to be determined. The unknown, i.e., the number of elements in the intersection, are given an algebraic numeral (such as x) and is then solved algebraically. Three sets are often involved.
EXAMPLE 1: Suppose there are 10 spectators at a ball game and 4 are wearing caps. How many spectators are not wearing caps?
Straightforward subtraction yields the result: 10 - 4 = 6. There are 6 spectators not wearing caps. Let us introduce mathematical notation that will, eventually, be helpful in expressing a generalization of this result.
If we use T to represent all spectators and C to represent the property "wearing a cap," we can apply conventional mathematics notation to represent the number of items or elements having the property: |T| = 10 and |C| = 4. We typically use a slash over the top of the letter to represent the complement of the property. [For this web page, we will use a tilda (~) to represent the complement.] So ~C is the property "not wearing a cap." This gives us |~C| = |T| - |C| = 10 - 4 = 6.
EXAMPLE 2: In the set S = {1,2,3,...,100}, how many elements are not divisible by 3?
Let's use D to represent the set of values divisible by 3. From the previous problem, it seems we need |~D| = |S| - |D|. We know |S| = 100. The set D = {3,6,9,...,99} and it has 33 elements. We get |~D| = 100-33 = 67. Therefore, 67 elements of S are not divisible by 3.