포함-배제 원리 (원본) (1)

[[분류:가져온 문서/오메가]]
Inclusion–exclusion principle

유한집합의 합집합의 원소의 개수를 나타내는 공식이다.

== 진술 ==
유한집합 [math(A_1,A_2,\cdots,A_n)]에 대해, 다음 식이 성립한다.
>[math(\displaystyle |A_1 \cup A_2 \cup \cdots \cup A_n|=\sum_{1\le i \le n}|A_i|-\sum_{1\le i<j \le n}|A_i\cap A_j| + \sum_{1\le i<j<k \le n}|A_i\cap A_j \cap A_k| +\cdots+(-1)^{n+1}|A_1\cap A_2\cap \cdots \cap A_n|)]
더 간단하게 표현하면,
>[math(\displaystyle \left\vert\bigcup_{i=1}^n A_i\right\vert=\sum_{k=1}^n(-1)^{k+1}\left( \sum_{1\le i_1 < <\cdots < i_k\le n}| A_{i_1}\cap\cdots\cap A_{i_k}|\right))]
을 얻는다.

== 영상 ==
[youtube(V9bcx6-XZKg)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]