포함-배제 원리

포함배제 원리 ➤ 포함-배제 원리

Inclusion–exclusion principle

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

목차

1. 진술
2. 영상

1. 진술 _{✎ ⊖}

유한집합

A_1,A_2,\cdots,A_n

에 대해, 다음 식이 성립한다.

$\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|$

더 간단하게 표현하면,

$\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)$

을 얻는다.

2. 영상 _{✎ ⊖}

이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.

1. 진술 ✎ ⊖

2. 영상 ✎ ⊖

1. 진술 _{✎ ⊖}

2. 영상 _{✎ ⊖}