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$ 개의 교집합의 원소의 개..

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Live of Thinking

Inclusion-Exclusion Principle

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역