포함배제의 원리는 중학교의 합의 법칙에서 등장하고, 고등학교에서 합집합의 원소 개수에 등장한다. 그리고 고등학교 통계 단원의 경우의 수를 계산하는 문제에서 중복되는 사건에 대한 경우를 중복 없이 셈할 때 사용한다. 이번 기회에 원리를 정확히 알고 이를 수학에서 어떻게 사용하는지 이해하는 시간이 되길 바란다.
개요
경우의 수와 포함배제의 원리
수학에서는 물론이고 실생활에서 어떤 것을 세어야 하는 경우가 많다. 어떤 경우의 수를 셀 때 자연수를 이용해 1부터 번호를 매기는 것이 가장 기본적인 방법이다.
하지만 일상에서 나열할 것이 너무 많거나 주어진 조건이 까다로운 경우 일일이 나열하기 쉽지 않다. 다양한 상황에 중복되어 있는 상황에서 경우의 수를 정확히 셀 수 있는 방법으로 포함배제의 원리에 대해 학습해 보자.
합의 법칙 이란?
경우의 수를 세는 방법으로 중학교 2학년 때 배우는 합의 법칙에 대해 아래 예제를 이용해 복습해 보기로 하자.
[예제] 주사위를 한 번 던질 때 다음의 경우의 수를 구하여라.
- 짝수 또는 5의 배수가 나오는 경우의 수.
- 짝수 또는 소수가 나오는 경우의 수.
[풀이]
- 짝수인 경우는 $2, 4, 6$ 이고 $5$의 배수인 경우는 $5$ 이므로 경우의 수는 $3+1=4$(가지) 이다.
- 짝수인 경우는 $2, 4, 6$ 이고 소수는 $2, 3, 5$ 이므로 동시에 만족하는 수를 나열하면 $2, 3, 4, 5, 6$ 이므로 $5$ (가지) 이다.
이 문제를 통해 알 수 있는 사실을 정리하면 다음과 같다.
$1$번 문제 처럼 두 조건을 동시에 만족하는 경우가 없다면 각 조건을 만족하는 경우의 수($3,\;1$)을 더하여 계산할 수 있다.
$2$번 문제 처럼 두 조건을 동시에 만족하는 경우가 있다면 각 조건을 만족하는 경우의 수($3,\;3$)을 더하고 주사위 눈이 2가 되는 상황은 두 번 더한 셈이므로 동시에 만족하는 경우의 수 $1$을 빼주면 된다.
이렇게 두 가지 경우의 수를 계산하는 방법을 합의 법칙이라고 하고 수학적으로 다음과 같이 정리한다.
[정리1] 통계에서 합의 법칙 (중2 통계)
두 조건 $A,\;B$ 를 만족하는 경우의 수가 $a,\;b$라고 할 때
- $A,\;B$를 동시에 만족하는 경우가 없다면
$A$ 또는 $B$를 만족하는 경우의 수 : $a+b$ - $A,\;B$를 동시에 만족하는 경우의 수가 $c$ 라면
$A$ 또는 $B$를 만족하는 경우의 수 : $a+b-c$
[정리2] 집합에서 합의 법칙 (고1 집합)
두 집합 $A,\;B$에 대하여
- $A\cap B=\phi$ 이면
$\left|A\cup B\right|=\left|A\right|+\left|B\right|$ - $A\cap B\neq\phi$ 이면
$\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A \cap B \right|$
단, $\left|A\right|$는 집합 $A$의 원소의 갯수를 의미한다.
벤다이어 그램 표현
두 집합 $A,\;B$에 대하여 벤다이어 그램을 그려 두 가지 경우를 생각하면 아래와 같다.
첫 번째 상황에서 $A\cap B=\phi$ 인 경우 $\left|A \cap B \right|=0$ 이다. 따라서 위의 두 가지 상황에 대한 이론을 아래와 같이 한번에 정리할 수 도 있다.
두 집합 $A,\;B$에 대하여
- $\left|A\cap B\right|=\left|A\right|+\left|B\right|-\left|A \cap B \right|$
[정리3] 세 집합의 원소의 개수
집합의 개수가 세 인 경우는 어떻게 원소의 개수를 구할 수 있을까?
- 먼저 각 집합의 원소의 개수를 구해서 더하자.
$\left|A\right|+\left|B\right|+\left|C\right|$ - $\left|A\cap B \right|,\;\left|B\cap C \right|,\;\left|A\cap C \right|$의 원소를 한번씩 뺀다.
$-\left|A\cap B \right|-\left|B\cap C \right|-\left|A\cap C \right|$ - $\left|A \cap B \cap C\right|$에 대해 생각하자.
1을 통해 $\left|A \cap B \cap C\right|$의 원소가 세 번 더해지고
2를 통해 $\left|A \cap B \cap C\right|$의 원소가 세 번 빠진다.
따라서 1+2 의 결과에 $\left|A \cap B \cap C\right|$을 한 번 더해야 한다.
이를 정리하면 다음과 같고 수학적으로 더 일반화 시켜 포함배제의 원리라고 한다..
[심화] 포함 배제의 원리
세 집합의 포함배제의 원리
세 집합 $A,\;B,\;C$에 대하여
- $\left| A \cup B \cup C \right|$
$= \left|A\right|+\left|B\right|+\left|C \right|$
$\;\;\;-\left (\left|A\cap B \right|+\left|B\cap C \right|+\left|A\cap C \right|\right)$
$\;\;\;+\left( \left|A \cap B \cap C\right|\right)$
네 집합의 포함배제의 원리
네 집합에 대해서는 어떻게 계산 할 수 있을까? 결과부터 정리하고 내용을 이해하기로 하자. 식이 복잡해 지므로 $\left|A\right|\rightarrow\;A$로 표기하고, $\left| A \cap B \right|\rightarrow\; AB$로 표기하기로 하자.
네 집합$A, \;B, \;C,\; D$에 대하여
- $\left| A \cup B \cup C \cup D \right|$
$=A+B+C+D$
$\;\;\;-(AB+AC+AD+BC+BD+CD)$
$\;\;\;+(ABC+ABD+ACD+BCD)$
$\;\;\;-ABCD$
네 집합에서 포함배제의 원리
$A,\;B,\;C,\;D$의 각 원소의 개수를 합하면 각 영역별로 원소가 중복해서 더 해지고 이를 벤다이어 그램에 표현하였다.
두 개 집합이 교집합인 부분을 한 번 씩 빼었을 때 각 영역별로 빼진 횟수를 표현하였다.
세 집합의 교집합 부분의 원소의 개수를 더해줄 때 각 영역의 원소들이 중복되어 더해지는 횟수를 표현하였다.
마지막으로 $A \cap B \cap C \cap D$ 의 원소의 개수를 생각하면 2번 중복되어 더해졌으므로 한번만 빼주면 위의 식을 통해 전체 영역의 원소를 한 번씩 셀 수 있다는 사실을 알 수 있다.
일반적으로 더 많은 집합에서도 합집합의 원소의 개수를 셀 때 교집합의 개수를 늘려가며 덧셈과 뺄셈을 반복하면 원하는 값을 얻을 수 있고, 이를 포함 배제의 원리라고 한다.
[전공수학] 포함배제의 원리
$A_{1},\;A_{2},\;A_{3}\cdots A_{n}$의 합집합의 원소 개수는 다음과 같다.
- $\left| A_{1} \cup A_{2} \cup \cdots \cup A_{n} \right|=S_{1}-S_{2}+ \cdots +(-1)^{n+1}S_{n}$
$S_{n}$ : n개 집합의 교집합의 원소 갯수 총합
$S_{1}=\sum\limits_{k=1}^{n}=\left|A_{1}\right|+\left|A_{2}\right|+\cdots +\left|A_{n}\right|$
$S_{2}=\sum\limits_{1\leq i \leq j \leq n}=\left|A_{1} \cap A_{2} \right|+\left|A_{1} \cap A_{3} \right|+\cdots+\left|A_{n-1} \cap A_{n} \right|$
$ \cdots $
$S_{n}=\left|A_{1} \cap A_{2} \cap \cdots \cap A_{n} \right|$
이에 대한 증명은 아래의 참고 자료로 대신 하도록 하겠다.
추가 학습 자료
마무리
수학에서 경우의 수를 헤아리는 가장 기초적인 방법인 포함배제의 원리를 완벽히 이해하는 시간이 되셨으면 합니다.