포함-배제의 원리 (Inclusion-Exclusion Principle)

포함-배제의 원리 (Inclusion-Exclusion Principle)

포함 배제의 원리는 조합론에서 여러 합집합의 크기를 계산하기 위해 사용하는 공식입니다.

기존 A와 B의 합집합을 A의 집합 + B의 집합 - A와B의 교집합으로 계산한 것과 같은 맥락으로, 이를 n개의 집합에서의 경우로 계산하는 방식입니다.

구조

A,B,C의 경우

A, B, C 3개의 집합에서 합집합의 크기는 다음과 같이 포함 배제의 공식을 통해 계산할 수 있습니다.

포함-배제의 원리 공식

공식은 수열을 통해 합집합의 크기를 계산합니다.

먼저 모든 집합을 더합니다. 그러면 더하는 과정에서 중복으로 더해지는 요소들이 존재합니다.

두 개의 다른 집합이 중복으로 보유하는 부분 -> 교집합이며, 이를 모든 집합에 대해 빼준다면 이번에는 더 빠지게 되는 부분이 존재합니다.

이를 집합의 크기만큼 번갈아가며 더하고 빼주어 중복 부위를 모두 제거하여 더하는 과정이 포함-배제의 원리입니다.

A, B, C의 경우 공식

출처: https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC