Combinatorics (Fall 2010)/Partitions, sieve methods

Principle of Inclusion-Exclusion

Let [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. For an [math]\displaystyle{ I\subseteq\{1,2,\ldots,n\} }[/math], we denote

[math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math]

with the convention that [math]\displaystyle{ A_\emptyset=U }[/math].

Principle of Inclusion-Exclusion

Let [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. Then the number of elements of [math]\displaystyle{ U }[/math] which lie in none of the subsets [math]\displaystyle{ A_i }[/math] is [math]\displaystyle{ \sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I| }[/math].

Let [math]\displaystyle{ S_k=\sum_{|I|=k}|A_I|\, }[/math]. Conventionally, [math]\displaystyle{ S_0=|A_\emptyset| }[/math]. The principle of inclusion-exclusion can be written as

[math]\displaystyle{ S_0-S_1+S_2+\cdots+(-1)^nS_n. }[/math]