[수학의 기초] 포함과 배제의 원리에 대하여 [더플러스수학학원]

올해도 울산과고1학년 1학기 중간고사에 경우의 수, 순열, 조합이 시험범위에 들어가게 되었다. 신입생들이 겨울방학동안 수학 상, 하를 열심히 공부했다고 하더라도 맨 마지막단원을 신경을 써서 공부하지는 않았던 것같고, 또, 중2의 확률과 경우의 수 단원을 유독 싫어했던 학생도 많은 듯하다. 그러나 이 단원은 어떤 특정한 기준-각자의 기준-에 따라 문제에서 구하고자 하는 경우의 수를 분류하고 그 분류기준에 따라 수를 빠짐없이 중복되지 않게 세야 한다. 

그러나 학생은 이 단원의 공식을 외우고 공식이 적용된 상황은 신경쓰지 않아서 많이 힘들어 한다. 또, 다음과 같은 문제를 보면 익숙하지 않다.

교란순열

$5$개의 숫자 $\displaystyle 1,~2,~3,~4,~5 $를 일렬로 나열한 것을 $\displaystyle a _ {1} ,~a _ {2} ,~a _ {3} ,~a _ {4} ,~a _ {5} $라고 할 때, $\displaystyle a _ {1} \neq 1$, $\displaystyle a _ {2} \neq 2$, $\displaystyle a _ {3} \neq 3$, $\displaystyle a _ {4} \neq 4$, $\displaystyle a _ {5} \neq 5 $를 모두 만족하는 경우의 수를 구하여라.

 

물론 위의 순열을 교란순열이라고 하며 중요한 문제이다. 여기서는 $\displaystyle a _ {1} \neq 1$, $\displaystyle a _ {2} \neq 2$, $\displaystyle a _ {3} \neq 3$, $\displaystyle a _ {4} \neq 4$, $\displaystyle a _ {5} \neq 5 $처럼 '부정(negative)'과 '그리고'(and)로 연결된 구문에 신경쓰자.

또, 다음과 같은 문제를 생각해 보자.

$\displaystyle  a,~b,~c,~d,~e $를 모두 사용하여 만든 다섯 자리 문자열 중에서 다음 세 조건을 만족하는 문자열의 개수를 구하여라.
(가) 첫째 자리에는 $\displaystyle  b $가 올 수 없다.
(나) 셋째 자리에는 $\displaystyle  a $도 올 수 없고 $\displaystyle  b $도 올 수 없다.
(다) 다섯째 자리에는 $\displaystyle  b $도 올 수 없고 $\displaystyle  c $도 올 수 없다.

 

위의 문제에도 밑줄치고 색칠한 부분처럼 '부정(negative)'과 '그리고'(and)로 연결된 구문이 있다. 이러한 구문을 포함하는 경우의 수를 구하는 문제에 적용되는 경우의 수를 세는 중요한 원리가 있다. 그것을 '포함과 배제의 원리'라고 한다.

포함과 배제의 원리란?

포함과 배제의 원리(1)
전체집합 $S$ 의 부분집합 $\displaystyle A_1,~ A_2, ~\cdots, ~A_m$ 에 대하여
$\displaystyle \begin{aligned} & n \left( A_1^c \cap A_2^c \cap \cdots \cap A_m^c \right) \\&=  n(S)-\sum n(A_i) \\&+\sum n \left(A_i \cap A_j\right) -\sum\left(A_i \cap A_j \cap A_k\right) \\ & +\cdots+\\&(-1)^m\left(A_1 \cap A_2 \cap \cdots \cap A_m\right) \end{aligned} $
(단, 첫째 $\displaystyle \sum$ 는 $i=1,~2,~ \cdots, ~m$ 에 관한 합이고, 둘째 $\displaystyle \sum$ 는 $\{i, ~j\}$ 에 관한 합 등이다.)

여기서 집합 \(A\)의 여집합을 \(A^c\), 집합 \(A\)의 원소의 개수를 \(n (A)\)라고 한다.

특징은 여러 집합의 여집합의 교집합의 원소의 개수를 구하는 것으로 여집합(부정의 형태-negative)의 교집합(그리고-and)의 꼴을 가지고 있다. 이것은 처음에 제시한 문제의 빨간색과 밑줄 친 부분에서 볼 수 있다.

먼저 집합이 \(2,~3\)개일 때의 꼴을 보면

$\displaystyle n \left(A_1^c \cap A_2^c \right)= n (S) - n(A_1 )-n(A_2 )+ n (A_1 \cap A_2 )$

$\displaystyle \begin{aligned}  n \left(A_1^c \cap A_2^c \cap A_3 ^c \right)  &= n (S) - n(A_1 )-n(A_2 )-n(A_3 )\\&+ n (A_1 \cap A_2 ) + n(A_2 \cap A_3 )\\&+n (A_3 \cap A_1 )\\&-n (A_1 \cap A_2 \cap A_3 )\end{aligned}$

 

위의 표현은 포함과 배제의 원리를 이용하여 경우의 수를 구하는 방법이다. 그리고 다음의 표현은 위와 동치이다. 증명도 아래의 경우로 하면 좀 더 쉽다.

포함과 배제의 원리(2)
전체집합 $S$ 의 부분집합 $\displaystyle A_1,~ A_2, ~\cdots, ~A_m$ 에 대하여
$\displaystyle \begin{aligned} n \left( A_1 \cup A_2 \cup \cdots \cup A_m \right) &= \sum n(A_i) -\sum n \left(A_i \cap A_j\right)+ \sum\left(A_i \cap A_j \cap A_k\right) \\ & +\cdots+(-1)^{m-1}\left(A_1 \cap A_2 \cap \cdots \cap A_m\right) \end{aligned} $

여기서 집합 \(A\)의 여집합을 \(A^c\), 집합 \(A\)의 원소의 개수를 \(n (A)\)라고 한다.

먼저 집합이 \(2,~3\)개일 때의 꼴을 보면

$\displaystyle n \left(A_1  \cup A_2 \right)=  n(A_1 )+n(A_2 )- n (A_1 \cap A_2 )$

$\displaystyle \begin{aligned}& n \left(A_1  \cup A_2  \cup A_3   \right) \\&= n(A_1 )+n(A_2 )+n(A_3 )\\&-n (A_1 \cap A_2 )- n(A_2 \cap A_3 )-n (A_3 \cap A_1 )\\&+n (A_1 \cap A_2 \cap A_3 )\end{aligned}$

수학적 귀납법으로 보여야 하는데 그냥 \(n=2\) 과정이 참이라 가정할 때, \(n=3\)일 때 참임을 보이자. 

$\displaystyle \begin{aligned} &n \left(A_1  \cup A_2  \cup A_3    \right) \\&= n \left\{(A_1  \cup A_2 ) \cup A_3    \right\}  \\&= n(A_1 \cup A_2 )+n(A_3 )-n \left\{ ( A_1 \cup A_2)\cap A_3 \right\}\\&=n(A_1 )+n(A_2 )-n (A_1 \cap A_2 ) +n(A_3)-n \left\{ ( A_1 \cap A_3 ) \cup (A_2\cap A_3)\right\} \\&=n(A_1 )+n(A_2 )-n (A_1 \cap A_2 ) +n(A_3)\\&-\left\{n(A_1 \cap A_3 )+n(A_2 \cap A_3 )  -n\left\{ (A_1 \cap A_3 ) \cap  (A_2 \cap A_3 ) \right\}\right\}\\&= n(A_1 )+n(A_2 )+n(A_3 )-n(A_1 \cap A_2 )-n(A_2 \cap A_3 )-n(A_3 \cap A_1 )\\&+n(A_1 \cap A_2 \cap A_3 ) \end{aligned}$

위의 과정과 비슷하게 수학적 귀납법을 이용하여 증명한다. 그런데 시그마 \(\displaystyle \sum\)의 기호를 가지고 설명해야 하니 익숙하지 않는 학생은 무엇이라고 적었는지 알 수 없어 당황스러울 것이다. 위의 내용을 참고하세요.

이제 위의 첫번째 문제를 분석해보자.

$5$개의 숫자 $\displaystyle 1,~2,~3,~4,~5 $를 일렬로 나열한 것을 $\displaystyle a _ {1} ,~a _ {2} ,~a _ {3} ,~a _ {4} ,~a _ {5} $라고 할 때, $\displaystyle a _ {1} \neq 1,~a _ {2} \neq 2,~a _ {3} \neq 3,~a _ {4} \neq 4,~a _ {5} \neq 5 $를 모두 만족하는 경우의 수를 구하여라.

 

(풀이) $\displaystyle a _ {1} = 1$인 집합을 $\displaystyle A _ {1}$, $\displaystyle a _ {2} = 2$인 집합을 $\displaystyle A _ {2}$, $\displaystyle a _ {3} = 1$인 집합을 $\displaystyle A _ {3}$, $\displaystyle a _ {4} = 4$인 집합을 $\displaystyle A _ {4}$, $\displaystyle a _ {5} = 5$인 집합을 $\displaystyle A _ {5}$라 하면 우리가 구하고자 하는 것은 집합 $\displaystyle A _ {1}^c \cap A_2 ^c \cap A_3^c \cap A_4^c \cap A_5^c $의 원소의 개수이다. 

포함과 배제의 원리를 이용하자. 먼저 $5$개의 숫자 $\displaystyle 1,~2,~3,~4,~5 $를 일렬로 나열한 집합을 \(S\)라 하면 \(n(S)=5!\), 또,

$\displaystyle n(A _ {1})=n(A_2 )=n(A_3 )=n(A_4)=n(A_5)= 4!$,

$\displaystyle \begin{aligned} &n(A _ {1} \cap A_2)=n(A_1 \cap A_3 )=n(A_1 \cap A_4 )=n(A_1 \cap A_5)\\&= n(A _ {2} \cap A_3)=n(A_2 \cap A_4 )=n(A_2 \cap A_5 )\\&=n(A_3 \cap A_4)=n(A_3 \cap A_5)=n(A_4 \cap A_5)\\& = 3! \end{aligned}$ 

즉, $\displaystyle {}_5 \mathrm C_2 \times 3! $

또, 예를 들면 $\displaystyle  n(A _ {1} \cap A_2 \cap A_3)=2!$ 이므로 $\displaystyle   A _ {i} \cap A_j \cap A_k $ 인 개수는 $\displaystyle  {}_5 \mathrm C_ 3 $ 이다. 따라서 $\displaystyle  {}_5 \mathrm C_3 \times 2!$

또, $\displaystyle  n(A _ {1} \cap A_2 \cap A_3 \cap A_4)=1!$이고 $4$개의 집합의 교집합의 개수는 $ {}_5 \mathrm C_4 $이므로 $\displaystyle  {}_5 \mathrm C_4 \times 1!$

또,  $\displaystyle  n(A _ {1} \cap A_2 \cap A_3 \cap A_4 \cap A_5)=0!$이고 $5$개의 집합의 교집합의 개수는 $ {}_5 \mathrm C_5 $이므로 $\displaystyle  {}_5 \mathrm C_5 \times 0!$

따라서 구하고자 한 개수는

$\displaystyle 5! -{}_5 \mathrm C_1 \times 4! +{}_5 \mathrm C_2 \times 3! -{}_5 \mathrm C_3 \times 2! +{}_5 \mathrm C_4 \times1!- {}_5 \mathrm C_5 \times0! $

 

또 다른 위의 문제를 보자.

$\displaystyle  a,~b,~c,~d,~e $를 모두 사용하여 만든 다섯 자리 문자열 중에서 다음 세 조건을 만족하는 문자열의 개수를 구하여라.
(가) 첫째 자리에는 $\displaystyle  b $가 올 수 없다.
(나) 셋째 자리에는 $\displaystyle  a $도 올 수 없고 $\displaystyle  b $도 올 수 없다.
(다) 다섯째 자리에는 $\displaystyle  b $도 올 수 없고 $\displaystyle  c $도 올 수 없다.

 

(풀이) $\displaystyle  a,~b,~c,~d,~e $를 모두 사용하여 만든 다섯 자리 문자열의 집합을 $S$라 하면 $n(S)= 5!$. 또, (가)를 만족하지 않는 집합을 $A_1$, (나)를 만족하지 않는 집합을 $A_2$, (다)를 만족하지 않는 집합을 $A_2$라 하면

$n(A_1)=(5-1)!$,

$A_2$는 세째자리에 $a$가 오거나 $b$가 오는 집합이다. 따라서 $n(A_2 )=2\times 4!$

$A_3$는 다섯째자리에 $b$가 오거나 $c$가 오는 집합이므로 $n(A_3 )=2\times 4!$

또, $A_1 \cap A_2$는 첫째 자리에 $b$가 오고 세째 자리에는 $a$ 또는 $b$ 가 오는 집합이다. 그런데 첫째 자리에 $b$가 오면 세째 자리에는 $b$가 오지 못하므로 $a$가 올 수밖에 없다. 따라서 $n(A_1 \cap A_2)=3!$

또, $A_1 \cap A_3$는 첫째 자리에 $b$가 오고 다섯째 자리에는 $b$ 또는 $c$ 가 오는 집합이다. 그런데 첫째 자리에 $b$가 오면 다섯째 자리에는 $b$가 오지 못하므로 $c$가 올 수밖에 없다. 따라서 $n(A_1 \cap A_3)=3!$

또, $A_2 \cap A_3$는 셋째 자리에 $a$ 또는 $b$가 오고 다섯째 자리에는 $b$ 또는 $c$ 가 오는 집합이다. 이 경우는 (세째자리, 다섯째자리)의 순서쌍은 $(a,~b)$ 또는  $(a,~c)$ 또는 $(b,~c)$이므로 $n(A_2 \cap A_3)=3\times 3!$

마지막으로 $A_1 \cap A_2 \cap A_3$는 첫째자리에 $b$, 세째자리에 $a$, 다섯째 자리에 $c$가 오므로 $n(A_1 \cap A_2 \cap A_3)=2!$이다. 따라서 포함과 배제의 원리에 의해 우리가 구하고자 하는 경우의 수는

$\begin{aligned}&n(S)-n(A_1)-n(A_2)-n(A_3) -n(A_1 \cap A_2) -n(A_2 \cap A_3)-n(A_3 \cap A_1)+ n(A_1 \cap A_2 \cap A_3)\\&= 5! - 4!-2\times 4!-2\times 4!+3!+3!+3\times 3! -2!\\& =28 \end{aligned}$

 

https://naver.me/xIhg4CMX

더플러스수학학원 : 네이버