위키득계정 ↗
과학

포함 배제 원리

포함 배제 원리과학
영문명
Inclusion-exclusion principle
대상
유한 집합의 합집합 크기
핵심
중복 계산의 보정
두 집합 식
|A| + |B| − |A∩B|
포함 배제 원리는 여러 유한 집합의 합집합 크기를 구할 때 중복해서 센 부분을 빼고 필요한 부분을 다시 더하는 원리다. 두 집합에서는 |A∪B|=|A|+|B|−|A∩B|가 된다.

두 번 센 원소

A의 원소가 8개, B의 원소가 7개이고 공통 원소가 3개라면 합집합의 원소 수는 8+7−3=12다. 공통 원소를 처음에 두 번 세었기 때문에 한 번 빼서 결과에 한 번만 남긴다.

세 집합의 경우

세 집합에서는 각 크기를 더하고 두 집합씩의 교집합 크기를 모두 뺀 뒤 세 집합의 공통 부분을 더한다. 세 집합에 모두 속한 원소는 처음에 세 번 더하고 세 번 빼졌으므로 마지막에 한 번 더해야 한다.

배수의 개수 세기

1부터 30까지에서 2 또는 3의 배수인 수는 15+10−5=20개다. 2와 3의 공배수는 6의 배수이고 그 수가 5개이므로 중복 계산을 보정한다.

무엇을 세는지 확인

합집합은 적어도 한 집합에 속한 원소를 센다. 정확히 한 집합에만 속한 원소의 수와는 다르다. 문제에서 또는과 정확히 하나의 조건을 구별해야 한다.

관련 문서

합집합 / 교집합 / 집합 / 경우의 수 / 합의 법칙 / 공배수 / 배수