Combinatorics (Fall 2010)/Partitions, sieve methods: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 1: | Line 1: | ||
== Principle of Inclusion-Exclusion == | == Principle of Inclusion-Exclusion == | ||
For an <math>I\subseteq\{1,2,\ldots,n\}</math>, we denote | |||
:<math>A_I=\bigcap_{i\in I}A_i</math>. | |||
{{Theorem|Principle of Inclusion-Exclusion| | |||
:Let <math>A_1,A_2,\ldots,A_n</math> be a family of subsets of <math>U</math>. Then the number of elements of <math>U</math> which lie in none of the subsets <math>A_i</math> is | |||
::<math>\sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I|</math>. | |||
}} | |||
== Permutations == | == Permutations == | ||
Revision as of 13:12, 14 July 2010
Principle of Inclusion-Exclusion
For an [math]\displaystyle{ I\subseteq\{1,2,\ldots,n\} }[/math], we denote
- [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/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{ 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