PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
principle of inclusion-exclusion (Theorem)

The principle of inclusion-exclusion provides a way of methodically counting the union of possibly non-disjoint sets.

Let $ C = \{A_1, A_2, \dots A_N\}$ be a finite collection of finite sets. Let $ I_k$ represent the set of $ k$-fold intersections of members of $ C$ (e.g., $ I_2$ contains all possible intersections of two sets chosen from $ C$).

Then

$\displaystyle \left\vert \bigcup_{i=1}^{N} A_i \right\vert = \sum_{j=1}^N \left( (-1)^{(j+1)} \sum_{S \in I_j} \vert S\vert \right )$

For example:

$\displaystyle \vert A \cup B\vert = \vert A\vert+\vert B\vert-\vert A \cap B\vert$
$\displaystyle \vert A \cup B \cup C\vert = \vert A\vert+\vert B\vert+\vert C\ve... ...\cap B\vert+\vert A \cap C\vert+\vert B \cap C\vert)+\vert A \cap B \cap C\vert$

The principle of inclusion-exclusion, combined with de Morgan's laws, can be used to count the intersection of sets as well. Let $ A$ be some universal set such that $ A_k \subseteq A$ for each $ k$, and let $ \overline{A_k}$ represent the complement of $ A_k$ with respect to $ A$. Then we have

$\displaystyle \left \vert \bigcap_{i=1}^N A_i \right \vert = \left \vert\overline{ \bigcup_{i=1}^N \overline{A_i} }\right \vert$

thereby turning the problem of finding an intersection into the problem of finding a union.



"principle of inclusion-exclusion" is owned by Mathprof. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: sieve of Eratosthenes, Brun's pure sieve

Other names:  inclusion-exclusion principle

Attachments:
proof of principle of inclusion-exclusion (Proof) by mps
Log in to rate this entry.
(view current ratings)

Cross-references: complement, universal, intersection of sets, de Morgan's laws, contains, intersections, represent, finite sets, collection, finite, union
There are 7 references to this entry.

This is version 6 of principle of inclusion-exclusion, born on 2002-03-28, modified 2007-06-28.
Object id is 2803, canonical name is PrincipleOfInclusionExclusion.
Accessed 11000 times total.

Classification:
AMS MSC: 05A99 (Combinatorics :: Enumerative combinatorics :: Miscellaneous)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)