Inclusion-Exclusion Principle (1) 썸네일형 리스트형 66. Inclusion-Exclusion Principle 포함-배제의 원리(Inclusion-Exclusion Principle)는 각 집합의 원소의 수를 이용하여 그것들의 합집합의 원소의 수를 구할 때 사용되는 원리이다. 포함-배제의 원리에 따르면 $n$개의 집합 $A_1, A_2, \ldots A_n$의 합집합의 원소의 개수는 다음과 같이 구할 수 있다. $$\left\vert \bigcup_{i=1}^n A_i \right\vert = \sum_{I \subset U} (-1)^{\left\vert I \right\vert +1} \left\vert \bigcap_{i \in I} A_i \right\vert$$ 이것을 해석하면, $n$개의 집합의 합집합의 원소의 개수는 $($집합 $1$개의 원소의 개수의 합$) - ($집합 $2$개의 교집합의 원소의 개.. 이전 1 다음
