포함배제의 원리

확률통계 고등 · 교육과정: 합집합의 개수를 겹친 부분을 빼며 세는 원리. 집합 두 개짜리 공식을 여러 개로 일반화한다. · v1 · 🤖 LLM 버전

이 개념은 합집합의 개수를 겹친 부분을 빼며 세는 원리이며, 집합 두 개짜리 공식을 여러 개의 집합으로 일반화한 것이다.

정의

유한집합 $A_1, A_2, \dots, A_n$에 대해, 합집합의 원소의 개수 $n(A_1 \cup A_2 \cup \cdots \cup A_n)$은 각 집합의 원소의 개수를 모두 더한 뒤, 두 집합씩 겹친 부분을 빼고, 세 집합씩 겹친 부분을 다시 더하고, ... 이런 식으로 번갈아 더하고 빼서 구할 수 있다. 이를 포함배제의 원리(inclusion-exclusion principle)라 한다.

집합이 두 개, 세 개일 때는 다음과 같다.

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

$$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A\cap B) - n(B\cap C) - n(C\cap A) + n(A\cap B\cap C)$$

직관

$n(A) + n(B)$를 그냥 더하면 $A \cap B$($A$ 교집합 $B$라 읽는다, $A$와 $B$에 동시에 속하는 원소들의 집합)에 속하는 원소가 두 번 세어진다. 벤 다이어그램을 그려 보면, $A$와 $B$가 겹치는 부분은 두 원 모두에 들어 있어서 두 번 색칠되는 것과 같다. 그래서 한 번 뺀 것이 $n(A)+n(B)-n(A\cap B)$다. 집합이 세 개, 네 개로 늘어나면 겹치는 방식도 복잡해지지만, 원리는 같다 — "더 세어진 만큼 빼고, 너무 많이 뺐으면 다시 더한다"를 반복하는 것뿐이다.

유도

두 집합의 경우 $n(A\cup B) = n(A)+n(B)-n(A\cap B)$는 이미 알고 있다. 이제 세 집합 $A, B, C$의 합집합을 구해보자.

$A \cup B$를 하나의 집합으로 보고 $C$와의 합집합에 두 집합 공식을 적용하면

$$n(A\cup B\cup C) = n\big((A\cup B)\cup C\big) = n(A\cup B) + n(C) - n\big((A\cup B)\cap C\big)$$

여기서 $n(A\cup B) = n(A)+n(B)-n(A\cap B)$이고, 분배법칙 $(A\cup B)\cap C = (A\cap C)\cup(B\cap C)$를 이용하면

$$n\big((A\cup B)\cap C\big) = n(A\cap C) + n(B\cap C) - n\big((A\cap C)\cap(B\cap C)\big) = n(A\cap C)+n(B\cap C)-n(A\cap B\cap C)$$

이 두 결과를 처음 식에 대입해서 정리하면

$$n(A\cup B\cup C) = n(A)+n(B)-n(A\cap B) + n(C) - \big[n(A\cap C)+n(B\cap C)-n(A\cap B\cap C)\big]$$

$$= n(A)+n(B)+n(C) - n(A\cap B) - n(B\cap C) - n(C\cap A) + n(A\cap B\cap C)$$

즉 원소 하나씩(1개짜리 교집합) 더하고, 두 개씩 겹친 것을 빼고, 세 개가 다 겹친 것을 다시 더하는 구조가 나온다. 이 패턴은 집합이 $n$개일 때도 그대로 이어져서, "$k$개의 집합을 고른 교집합의 개수를 모두 더한 값"에 $(-1)^{k+1}$의 부호를 붙여 합한 것이 전체 합집합의 개수가 된다.

성질

• 집합이 늘어나도 부호는 홀수 개를 고르면 $+$, 짝수 개를 고르면 $-$로 번갈아 나타난다.
• 모든 교집합이 공집합이면(서로소이면) 포함배제의 원리는 그냥 $n(A_1)+n(A_2)+\cdots+n(A_n)$이 된다 — 뺄 것이 없어지는 특수한 경우다.

예시

1부터 100까지의 자연수 중 2의 배수 또는 3의 배수의 개수를 구해보자. $A$를 2의 배수의 집합, $B$를 3의 배수의 집합이라 하면

$$n(A) = 50,\quad n(B) = 33,\quad n(A\cap B) = 16\ (\text{6의 배수의 개수})$$

$$n(A\cup B) = 50 + 33 - 16 = 67$$

집합 세 개짜리 예로, 1부터 30까지의 수 중 2, 3, 5 중 적어도 하나로 나누어지는 수의 개수를 구해보면 $n(A)=15, n(B)=10, n(C)=6$, $n(A\cap B)=5, n(B\cap C)=2, n(C\cap A)=3$, $n(A\cap B\cap C)=1$이므로

$$15+10+6-5-2-3+1 = 22$$

🌍 실생활 예시

설문조사에서 "영어를 할 수 있는 사람 200명, 프랑스어를 할 수 있는 사람 150명, 두 언어를 다 할 수 있는 사람 60명"이라는 결과가 있으면, 적어도 한 언어를 할 수 있는 사람의 수는 $200+150-60=290$명이다. 이렇게 여러 조건(자격증, 구독 서비스, 질병 보유 여부 등)이 겹치는 통계를 집계할 때 포함배제의 원리가 실제로 쓰인다.

⚠️ 흔한 실수

• $n(A\cup B) = n(A)+n(B)$로 그냥 더한다: $A$와 $B$에 공통으로 속하는 원소가 있으면 두 번 세어지므로, 반드시 $n(A\cap B)$를 빼야 한다. 두 집합이 서로소일 때만 그냥 더해도 맞는다.
• 세 집합에서 두 개씩 교집합만 빼고 끝낸다: $n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)$까지만 계산하면, 세 집합이 모두 겹치는 부분($A\cap B\cap C$)이 세 번 더해졌다가 세 번 빼져서 결국 안 세어진 상태가 된다. 그래서 $+n(A\cap B\cap C)$를 마지막에 다시 더해야 한다.
• "적어도 하나"와 "정확히 하나"를 혼동한다: 포함배제의 원리로 구한 $n(A\cup B\cup C)$는 "적어도 하나의 조건을 만족하는" 개수다. "정확히 한 조건만 만족하는" 개수를 구하려면 별도로 겹치는 부분들을 빼주는 계산이 더 필요하다.

확인 문제

1. 1부터 50까지의 자연수 중 3의 배수 또는 4의 배수의 개수를 구하시오.
2. 두 집합 공식 $n(A\cup B)=n(A)+n(B)-n(A\cap B)$를 이용해서, 세 집합 공식의 마지막 항 $+n(A\cap B\cap C)$가 왜 붙는지 벤 다이어그램의 각 영역이 몇 번씩 더해지고 빼지는지 직접 세어보며 설명하시오.
3. 어느 반 학생 30명 중 축구를 좋아하는 학생이 18명, 야구를 좋아하는 학생이 15명, 둘 다 좋아하는 학생이 8명이다. 둘 다 좋아하지 않는 학생은 몇 명인가?

📜 역사

포함배제의 원리는 특정 한 사람이 어느 한 시점에 발표한 정리라기보다, 조합론에서 "겹치는 경우를 중복 없이 세는" 문제를 다루면서 자연스럽게 정리된 계산 규칙이다. 두 집합에 대한 형태는 벤 다이어그램으로도 직관적으로 이해되어 오래전부터 쓰였고, 여러 집합으로 일반화된 형태는 18~19세기 조합론과 정수론(예: 오일러 파이 함수 계산)에서 정수의 배수 개수를 세는 데 활용되며 체계화되었다. 현재는 조합론뿐 아니라 확률론, 정수론, 컴퓨터과학의 알고리즘 문제에서도 폭넓게 쓰인다.

관련 개념

• 경우의 수와 확률의 기초: 두 집합짜리 포함배제 공식이 기대는 합의 법칙이 여기서 나온다.
• 경우의 수: 포함배제의 원리는 결국 경우의 수를 중복 없이 세는 방법 중 하나다.
• 비둘기집 원리: 같은 조합론 단원에서 함께 다뤄지는 원소 개수 논증 방법이다.
• 확률: 사건의 합집합의 확률을 구할 때도 같은 형태의 공식이 쓰인다.