B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

PRINCIPLE OF INCLUSION-EXCLUSION:

The Principle of Inclusion and Exclusion allows us to find the cardinality of a union of sets by knowing the cardinalities of the individual sets and all possible intersections of them.

The basic version of the Principle of Inclusion and Exclusion is that for two finite sets A and B, is

|A∪B|=|A|+|B|–|A∩B|.

The result generalizes to three finite sets (in fact it generalizes to any finite number of finite sets):

|A∪B∪C|=|A|+|B|+|C|–|A∩B|–|A∩C|–|B∩C|+|A∩B∩C|

Example :
In a room of 50 people whose dresses have either red or white color, 30 are wearing red dress, 16 are wearing a combination of red and white. How many are wearing dresses that have only white color?

Solution

Number of people wearing a red dress = 30 i.e., n(R) = 30

Number of people wearing a combination of red and white = 16 i.e., n (R W) = 16

The total number of people in the room = number of people who are wearing dresses that have either red or white colour = n (R W) = 50.

We know,
n (R W) = n(R) + n(W) - n(R W) 50 = 30 + n(W) - 16

50 - 14 = n(W) - 16

n(W) = 36

i.e., the number of people who are wearing a white dress = 36.

Therefore, number of people who are wearing white dress only = n(W) - n(R W) =
36 - 16 = 20