포함과 배제의 원리

이 항목의 수학노트 원문주소

개요

\(|A\cup B| = |A| + |B| - |A \cap B|\)
\(|A\cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|\)
일반적으로 집합 A의 부분집합 \(A_i\)에 대하여, 다음이 성립한다.
\(\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|\)

뫼비우스 반전공식 의 특별한 경우로 이해할 수 있다

증명

집합 A의 부분집합 \(A_i\)에 대하여, 다음이 성립한다

\(\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|\)

(증명)

\(a\in \bigcup_{i=1}^n A_i\) 가 \(A_i\) 들 중 k 개의 집합에 속해 있으면, a 는 우변을 통하여 \(\sum _{l=1}^k (-1)^{l-1} \binom{k}{l}=1\) 번 세어지게 된다. ■

포함과 배제의 원리

목차

이 항목의 수학노트 원문주소

개요

증명

응용

역사

메모

관련된 항목들

수학용어번역

사전 형태의 자료

리뷰논문, 에세이, 강의노트

관련논문

관련도서

둘러보기 메뉴

검색