Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



The Inclusion-Exclusion Principle


Our goal here is to efficiently determine the number of elements in a set that possess none of a specified list of properties or characteristics. We begin with several examples to generate patterns that will lead to a generalization, extension, and application.

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.

EXAMPLE 3: Among 10 students, 5 study mathematics, 6 study science, and 2 study both. How many of these students study neither mathematics nor science?

For this problem, we first refer to a Venn diagram, a visual tool we could have employed in the first two examples as well. In the figure here we represent each property with a circle, and the portion on the circles that overlap, or intersect, represents elements with both the properties. We use T to represent the entire group of students, M to represent the property "study mathematics" and S to represent the property "study science."

We know there are 2 people who study both mathematics and science, so we place a 2 at the intersection of the two properties (circles). We must then have 3 who study mathematics but not science (because 5 in all study mathematics), and 4 who study science but not mathematics (because 6 in all study science). This accounts for 9 people, so the remaining 1 person must study neither mathematics nor science.

This is a relatively straightforward determination, especially with the aid of the Venn diagram. How do our calculations compare to those made in the first two examples? We have |T| = 10, |M| = 5, |S| = 6, and |M^S| = 2. [Note that on this web page we use ^ to represent the intersection of two sets. Normally this is an inverted U.]

But |~M^~S| is not equal to |T| - (|M| + |S|), a pattern we might have tried based on the first two examples. Why is this insufficient? Look back at the Venn diagram. When we subtract |M| and |S| from |T|, we are twice subtracting the number of elements in the intersection of the two sets. That is the value 2 here, or in general, |M^S|. To compensate for the "over" subtraction, we add back |M^S|, as follows: |~M^~S| = |T| - (|M| + S|) + |M^S|.

EXAMPLE 4: Among 18 students in a room, 7 study mathematics, 10 study science, and 10 study computer programming. Also, 3 study mathematics and science, 4 study mathematics and computer programming, and 5 study science and computer programming. We know that 1 student studies all three subjects. How many of these students study none of the three subjects?

We are looking for |~M^~S^~C|, where M, S, and C represent belonging to the group that studies each of the three subjects mathematics, science, and computer programming, respectively. Consider the Venn diagram below. Can you justify each entry in the diagram, starting from knowing that |M^S^C| = 1? How many students study none of the three subjects?

Trying to use and generalize the patterns we've established above, consider |M| + |S| + |C|. What values are "over counted" here? When we subtract |M ^ S| + |M ^ C| + |S ^ C| from |M| + |S| + |C| to compensate, what values are "over" subtracted? What can be done to compensate for this?

EXAMPLE 5: Extend the patterns generated thus far in order to solve the following problem. Draw a Venn diagram if desired.

In a mathematics department of size 40, faculty are members of four different professional organizations: NCTM (N), MAA (M), AMS (A), and SSMA (S). We know that 21 are members of NCTM, 26 are MAA members, 19 belong to AMS, and 17 are in SSMA. In addition, we know that 15 are in both NCTM and MAA, 6 are in NCTM and AMA, 9 are in NCTM and SSMA, 14 and in MAA and AMS, 10 are in MAA and SSMA, and 11 are in AMS and SSMA. We also know that 6 are in NCTM, MAA, and AMS, 5 are in NCTM, MAA, and SSMA, 4 are in NCTM, AMS, and SSMA, and 9 are in MAA, AMS, and SSMA. finally, 4 people belong to all four organizations. How many faculty members belong to none of these organizations?

EXAMPLE 6: Extend the patterns developed thus far to write a general formula for determining the number of items in a set that possess none of k properties maintained by the set. This is the Inclusion-Exclusion Principle.

EXAMPLE 7: Manipulate the results you generated in Example 6 to determine the number of items in a set that possess at least one of the k properties maintained by the set.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes