The Inclusion Exclusion Principle

The rule of addition says how many elements are in a union of sets if the sets are mutually disjoint. But there exist cases where one has to determine
the number of elements in a union of sets when some of the sets overlap.

Let us consider  the union of two sets A and B. The number of elements in the union of the two sets varies according to the  number of elements
in each set that are common. If A and B have no common elements at all then the number of elements in their union will be the algebraic sum of the
number of elements of A and the number of elements of B, which is better represented by n(A U B) = n(A) + n(B)

If A and B are exactly the same sets, i.e if they coincide, then  n(AUB) =  n(A) .Thereby any formula for the number of elements in a union of two
sets must contain a reference to the number of elements that are common, n(A B) and also references to the number of individual elements of the
sets,n(A) and n(B).

To derive a formula for the number of elements in the union of the two sets, the number of elements in set A - n(A), which counts the elements in
A, the elements not in B and the elements that are both in A and B, along with  n(B), which counts the elements in A, the number of elements not
in A and the elements that are in both A and B are considered. By adding n(A) and n(B), the elements in both A and B are counted twice.
To eliminate this redundancy and get the value for n(AUB), we need to subtract the number of elements which are both in A and B, which is
represented by their intersection AB,
 

Therefore    n(AUB)=n(A) + n(B) - n(A B)

Definition
 

The Inclusion Exclusion  Principle for Two or Three Sets  Let P , Q  be finite sets, then  n(PUQ)=n(P) + n(Q) - n(P Q) and for three sets P, Q  and R  n(P U Q U R) = n(P) + n(Q) + n(R) - n(P Q) - n(P R) - n(Q R) +n(P  Q  R)

 
 
 
   
 
 

 
Example 1:
Counting the number of elements in a Union.
How many integers from 1 to 1000 are either multiples of  3 or multiples of 5

Solution
        Let us assume that A = set of all integers from 1-1000 that are multiples of 3
        Let us assume that B = set of all integers from 1-1000 that are multiples of 5
    From this we have A U B = The set of all integers from 1 to 1000 that are multiples of either 3 or 5
    and we also have
        (A B) = The set of all integers that are both multiples of 3 and 5, which also is the set of integers that are multiples of 15.

    To use the inclusion/exclusion principle to obtain n(A U B) , we need n(A),n(B) and n(A B)
    From 1 to 1000, every third integer is a multiple of 3,each of this multiple can be represented as 3p, for any integer p from 1 through 333.
    From the above we have that n(A) = 333 for integers 1-1000

    Similarly for multiples of 5, each multiple of 5 is of the form 5q for some integer q from 1 through 200.
    From this we have n(B) = 200

    For n(A B) , we need to determine the number of multiples of 15 from 1 through 1000. Each multiple of 15 is of the form 15r for
    some integer r from 1 through 66.
    Now we have the values for n(A B), which is 66.
 
    From all the above we can determine n(AUB), using the Inclusion/Exclusion  principle.

n(AUB) = n(A) + n(B) - n(A B)

Example2:
Counting the number of elements in an Intersection.
    In a class of students undergoing a computer course the following were observed.
    Out of a total of 50 students:
    30 know Pascal,
    18 know Fortran,
    26 know COBOL,
    9 know both Pascal and Fortran,
    16 know both Pascal and COBOL,
    8 know both Fortran and COBOL,
    47 know at least one of the three languages.
From this we have to determine
    a. How many students know none of these languages ?
    b. How many students know all three languages ?

a. We know that 47 students know at least one of the three languages in the class of 50. The number of students who do not know
    any of three languages is given by the difference between the number of students in class and the number of students who know
    at least one language.
                                                                    Hence 50 - 47 = 3

b. Let us assume that A = All the students who know Pascal in class.
                                B = All the students who know COBOL in the class.
                                C = All the students who know FORTRAN in class.

By applying the Inclusion exclusion principle,
 

n(AUBUC) = n(A) + n(B) + n(C) -n(AB) -n(AC) -n(BC)+n(ABC)

47 = 30 + 26 + 18 -9 -16 -8 + n(ABC)

n(ABC),

n(ABC) = 6