3.2 일반화된 포함과 배제의 원리

다음과 같은 '일반화된 포함배제의 원리'의 서술이 가능하다. 이것에 대한 일반적인 증명은 하지 않는다. 궁금한 독자는 조합론 서적을 참조하기 바란다.  

집합 $S$를 $n$개의 원소를 가지는 '전체집합'이라고 하고, 성질$1, 2, \cdots, q$를 생각하자. $m=0,1,2,\cdots,q$ 에 대하여, 다음이 성립한다.

   $\begin{align} E(m) = \omega(m) - C(m+1,m)\cdot \omega(m+1) \\  \\+ C(m+2,m)\cdot \omega(m+2)+\cdots \\ \\ \cdots+(-1)^{q-m}\cdot C(q,m)\cdot \omega(q) \end{align}$

식이 길고 시각적인 난해함에 매혹되어 머리가 아파지지 않도록 하자. 일반 독자에게 이런 수식의 사용은 달갑지 않은 것이지만 실제 수학 지식에 접근하게 될 때 우리는 수와 식이라는 장벽을 마주하게 된다. 수학을 배우려면 익숙해져야 하는 부분이다. 피할수 없다. 글로만 읽는 수학은 사실 별로 도움이 안 된다. 연필을 들고 종이 위에 사유할 여유를 가지기를 바란다. 

여기서 특히, $m=0$인 경우가 주로 사용된다.

이 식을 외워서 사용하는 것은 추천하지 않는다. 장담하건데,  그것은 수학을 어렵고 지겨운 것으로 만든다. 

   $E(0) = \omega(0) - \omega(1) + \omega(2) - \cdots + \cdots +(-1)^q \cdot \omega(q)$  

앞의 예(3.1 포함과 배제의 원리)에서 2의 배수의 집합을 $A$,  3의 배수의 집합을 $B$, 5의 배수의 집합을 $C$라 할 때, 
    $n(S) = E(0) + n(A\cup B\cup C)$, $S=\left\{1, 2, 3, \cdots, 500 \right\}$
이다. 또한,
   $\omega(0) = n(S) = n$  
   $\omega(1) = n(A)+n(B)+n(C)$
   $\omega(2) = n(A\cap B)+n(B\cap C)+n(C\cap A)$
   $\omega(3) = n(A\cap B\cap C)$
이므로 우리는
   $E(0) = \omega(0)-\omega(1)+\omega(2)-\omega(3)$
임을 확인할 수 있다. 

---

일반화된 포함배제의 원리의 이해를 돕기위해 이 원리를 적용하여 다음 예제를 풀어보자. 

예제) 다음 방정식의 음이 아닌 정수해의 개수를 구하여라. 단, $x_1\leq5, x_2\leq6, x_3\leq7$이다. 
   $x_1 + x_2 + x_3 = 15$

 

제1장에서 위의 방정식의 음이 아닌 정수해의 개수는 다른 부가조건이 없을 때, $H(3,15)$로 계산된다는 것을 공부했다. 그러나 위의 예제에서는 부가조건이 포함되어 있다.

 

우선, 집합 $S$를 위의 방정식의 음이 아닌 정수해들의 집합이라 하면, 그 원소들의 다음과 같은 순서쌍들의 집합이다. 
   $(x_1, x_2, x_3)$, $n(S)=H(3,15)$

 

우리의 $S$의 원소들에 대하여 다음과 같은 3개의 성질을 정의할 수 있다. 각 성질을 만족하는 원소들의 모임은 다음 $S$의 부분집합으로 표시된다.

     A ; $x_1\geq6$

     B ; $x_2\geq7$ 

     C ; $x_3\geq 8$ 

그러므로 문제에서 주어진 조건을 만족하는 정수해의 개수는 [성질A], [성질B], [성질C] 중 어떤 성질도 갖지 않는 원소들의 개수와 같다. 이것은 일반화된 포함과 배제의 원리에서 $E(0)$인 경우에 해당한다.

     $\omega(0) = n(S) = H(3,15)$

     $\omega(1) = n(A) + n(B) + n(C) = H(3,9) + H(3,8) + H(3,7)$

     $\omega(2) = n(A\cap B) + n(B\cap C) + n(C\cap A) = H(3,2) + H(3,1) + H(3,0)$

     $\omega(3) = n(A\cap B\cap C)=0$ 

그러므로

     $\begin{align} E(0) &= \omega(0) - \omega(1) + \omega(2) - \omega(3) \\ &= H(3,15)-H(3,9)-H(3,8)-H(3,7)+H(3,2)+H(3,1)+H(3,0) \\&=10 \end{align}$

이다.

 

일반화된 포함과 배제의 원리를 적용하기 위해서는 먼저, 문제에서의 전체집합 $S$가 무엇인지 알아야 하고, 다음으로 $S$의 원소들에 대해 '적절한' 성질을 정의해야 한다. 위의 문제에서, 설정한 성질들은 문제에서 요구하는 조건의 여집합이었다. 성질을 이렇게 정의함으로써, 문제에서 요구하는 조건을 만족하는 정수해가 우리가 설정한 성질들 중 '그 어떤 성질도 갖지 않는' $S$의 원소가 되도록 하였다.

 

일반화된 포함과 배재의 원리를 이용하면 자연스런 절차에 따른 풀이를 얻을 수 있다. 그러나 이것은 이 풀이가 항상 더 간단하다는 것을 의미하지는 않는다.

 

사실상 우리는 이 예제를 보통 다음과 같이 간단히 푼다.  
   $t_1 = 5 - x_1$
   $t_2 = 6 - x_2$  
   $t_3 = 7 - x_3$
그러면 주어진 식은 
   $t_1 + t_2 + t_3 = 3$  
이 되고, $0\leq t_1\leq 5$, $0\leq t_1\leq 6$, $0\leq t_7\leq 7$이 된다. 그런데, 이 부가조건은 아무런 역활을 하지 못한다. 따라서 요구되는 답은 
   $H(3,3)=10$
이다.