the principle of inclusion and exclusion

이 글에서는 포함-배제의 원리를 일반적이고 명확하게 기술해보고 포함-배제 원리의 산뜻한 증명을 시도해 본다. 이 글에서 소개한 산뜻한 증명은 참고문헌 [1]을 바탕으로 작성한 것이다. 포함-배제의 원리를 산뜻하게 기술하기 학교수학에서는 포함-배제의 원리를 다음과 같이 소개하곤 한다. 포함-배제의 원리(중,고등학교 버전) 유한개의 원소를 갖는 집합 $A, B$에 대하여 \( \vert A\cup B\vert=\vert A\vert +\vert B\vert - \vert A\cap B\vert\) 가 성립한다. 또한 유한개의 원소를…

Lemma for PIE. 원소의 개수가 \(t\)인 전체집합이 주어져있을 때, 전체집합의 부분집합 \(A, B, C, \ldots, Z\)의 어느 것에도 속하지 않는 원소의 개수는 t \)\( -(\vert A\vert+\vert B\vert+\vert C\vert+\cdots+\vert Z\vert) \)\( +(\vert A\cap B\vert+\vert A\cap C\vert+\cdots+\vert Y\cap Z\vert) \)\( -(\vert A\cap B\cap C\vert+\vert A\cap B\cap D\vert+\cdots+\vert X\cap Y\cap Z\vert) \)\( +(\vert A\cap B\cap C\cap D\vert+\cdots+\vert…

아래에 있는 그림에 관한 이야기로 이야기를 시작해보자. 원소를 \(t\)개 갖고 있는 어떤 전체집합이 있고 그 전체집합의 세 부분집합 \(A, B, C\)가 있을 때, 원소의 개수와 관련된 성질을 관찰해보자. 그림의 직사각형은 전체집합을 나타낸다. 각각의 집합 \(S\)에 대하여, \(S\)의 원소의 개수를 \(\vert S\vert\)로 나타내며 이를 집합 \(S\)의 크기(size)라고 말한다. 그림에 있는 세 개의 다이어그램에서 첫 번째를 보면 자명하면서도 매우 중요한 성질을 찾을…