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에 따라 이용할 수 있습니다.




(돌아가기)
(임시 저장) (임시 저장 불러오기)


(↪️) (💎) (🛠️) (추가)


비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.