Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 6E / ii

Table of contents
- Solution ii

Solution

For finitely many finite sets

A_{1}, \dots, A_{k}

, the inclusion-exclusion principle states

i = 1 ⋃ k A_{i} = \emptyset \neq = J \subseteq {1, \dots, k} \sum (- 1)^{∣ J ∣ + 1} j \in J ⋂ A_{j} .

To see why, an element belonging to exactly

t \geq 1

of the sets contributes

\sum_{j = 1}^{t} (- 1)^{j + 1} (j t) = 1

by the binomial theorem. Elements outside the union contribute zero. Equivalently, if these sets lie in a finite universe

U

, the number avoiding all of them is

∣ U ∣ + \sum_{\emptyset \neq = J} (- 1)^{∣ J ∣} ⋂_{j \in J} A_{j} .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version