The principle of Inclusion Exclusion

Inclusion Exclusion Rule

|A_{1} \cup A_{2} \cup . . . \cup A_{n}| \equiv \sum_{1 \leq i \leq n} A_{i} - \sum_{i \neq j} |A_{i} \cap A_{j}| + \sum_{d i f f e r e n t (i, j, k)} |A_{i} \cap A_{j} \cap A_{k}| - . . . . . . . .

* If the number of elements where none of the properties

A_{1}, A_{2}, . . ., A_{n}

happens is denoted by

N (A_{1}^{'} A_{2}^{'} . . . A_{n}^{'})

Then

N (A_{1}^{'} A_{2}^{'} . . . A_{n}^{'}) \equiv N - N (A_{1} \cup A_{2} \cup . . . \cup A_{n})

That is mean

= N - \underset{1 \leq i \leq n}{\sum N (A_{i})} + \sum_{i \neq j} N (A_{i} \cap A_{j}) - \sum_{d i f f e r e n t (i, j, k)} N (A_{i} \cap A_{j} \cap A_{k}) - . . . . . . . .

N (A_{i}) = # o f e l e m e n t s w h e r e A_{i} h a p p e n s .

N (A_{i} \cap A_{j}) = # o f e l e m e n t s w h e r e A_{i} & A_{j} h a p p e n s .

N (A_{i} \cap A_{j} \cap A_{k}) = # o f e l e m e n t s w h e r e A_{i} & A_{j} & A_{k} h a p p e n s .

.

.

.etc