Principle of inclusion-exclusion

 

Let's apply some of our knowledge about sets to counting finite sets. The size of a set S is called its cardinality, which we'll denote by

|S|.

For example, if S = {a, b, c}, then |S| = | {a, b, c} | = 3. We can say "the cardinality of S is 3," or 3 is the cardinal number of S," or simply "S has three elements."

Suppose we want to count the union of two sets. For example, suppose we have A = {1, 2, 3, 4, 5} and B = { 2, 4, 6, 8}. Since  , it follows that .

Similarly, since , it follows that . If we know any three of the four numbers |A|, |B|,  and , then we can find the fourth by using the following counting rule for finite sets:

 

Union Rule

                                                                             (1.6)

 

It's easy to discover this rule by drawing a Venn diagram.

The union rule extends to three or more sets. For example, the following calculation gives the union rule for three finite sets:

 

                                (1.7)

 

The popular name for the union rule and its extensions to three or more sets is the principle of inclusion and exclusion. The name is appropriate because the rule says to add (include) the count of each individual set. Then subtract (exclude) the count of all intersecting pairs of sets. Next, include the count of all intersections of three sets. Then exclude the count of all intersections of four sets, and so on.

EXAMPLE 1 (A Building Project). Suppose A, B and Ñ are sets of tools needed by three workers on a job. For convenience let's call the workers A, B, and C. Suppose further that the workers share some of the tools (for example, on a housing project, all three workers might share a single table saw). Suppose that A uses 8 tools, B uses 10 tools, and C uses 5 tools. Suppose further that A and B share 3 tools, A and C share 2 tools, and B and C share 2 tools. Finally, suppose that A, B, and C share the use of 2 tools. How many distinct tools are necessary to do the job? Thus we want to find the value .

We can apply the inclusion exclusion principle (1.7) to compute the answer:

 

 

 

EXAMPLE 2 (Surveys). Suppose we survey 200 students to see whether they are taking courses in computer science, mathematics, or physics. The results show that 90 students take computer science, 110 take mathematics, and 60 take physics. Further, 20 students take computer science and mathematics, 20 take computer science and physics, and 30 take mathematics and physics. We are interested in those students that take courses in all three areas. Do we have enough information? Let C, M, and P stand for the sets of students that take computer science, mathematics, and physics. So we are interested in the number .

From the information given we know that . The reason for the inequality is that some students may not be taking any courses in the three areas. The statistics also give us the following information:

 

; ; ;

; ; .

Applying the inclusion-exclusion principle (1.7), we have

 

 

Therefore . So we can say that at most 10 of the students polled take courses in all three areas. We would get an exact answer if we knew that each student in the survey took at least one course from one of the three areas.