30명의 회원이 있는 스포츠 클럽이 있다.

회원 중 20명은 tennis, 18명은 golf를 한다. 이 때,

10명은 tennis와  golf를 모두 한다면, 회원 중

tennis나 golf중 어느 한 가지도 하지 않는 회원은

모두 몇 명인가 알아보시오.

     많은 간접적인 수 세기의 방법 중에서 가장 기본적이며

 광범위한 응용을 갖는 세기의 방법인 포함배제의 원리에

 대하여 학습한다.

          포함배제의 원리

많은 간접적인 수 세기의 방법 중에서 가장 기본적이며

광범위한 응용을 갖는 세기의 방법에 대하여 알아봅시다.

임의의 집합 S 에 대하여 n(S) 를 집합  S 의 원소의 개수를 나타낸다고

하자.  이 때, n 개의  집합 S_1,S_2, ..., S_n 이 주어졌을 때,

n ( S₁ ∪ S₂ ∪ ... ∪ S_n )

을 구하여 봅시다.

먼저 얼마나 많은 원소들이 겹쳐 있는가를 알아보아야 된다. 만일 집합이

S_1, S₂  두 개인 경우에는

임을 쉽게 알 수 있다.  따라서 세 집합  S₁,S₂,S₃  에 대하여

집합의 연산법칙(De Morgan의 정리)에 의하여

이므로,

⁾

     위의 식을 일반화하면 다음의  포함배제의 원리  

(the principle of inclusion and exclusion)를  얻을 수 있다.

  증명은 다음을 참고하여 수학적 귀납법을 사용하여 각자 써 보시오.

 아래에서 A'은 A의 여집합을 나타낸다.

The principle of Inclusion and Exclusion :

  N(α'₁ α'₂ ... α'_n-1α'_n) = N - N(α₁) - N(α₂)- ... - N(αn)

+N(α₁α₂) +N(α₁α₃) + ... + N(α_n-1α_n)

-N(α₁α₂α₃) -N(α₁α₂α₄) - ... - N(α_n-2α_n-1α_n)

+ ...  ...  ...

+(-1)ⁿ N(α₁α₂ ...α_n-1α_n).                   (3.1)

Proof. The proof is by induction on the number of properties, that is , on the number n. if n=1 the formula is  N(α'₁ )=N-N(α₁ ) , which is obvioulsy true. Suppose (3.1) is true for n-1 properties. Using the formula on the objects that have a property α₁  . we obtain.  

N(α'₁α'₂ ...α'_n-1α_n)=

N(α_n)-N(α₁α_n)-N(α₂α_n)-...-N(α_N-1α_n)+

N(α₁α₂α_n)+N(α₁α₃α_n)+...+N(α_n-2α_n-1α_n)+

  ... ... ... ...

+(-1)^n-2 N(α₁α₂ ...α_n-2α_n)+...

+(-1)^n-2 N(α₂α₃ ...α_n-1α_n)+

(-1)^n-1 N(α₁α₂ ...α_n-1α_n).                          (3.2)

We also have

N(α'₁α'₂ ...α'_n-1) = N - N(α₁)-N(α₂)-...-N(α_n-1)

+N(α₁α₂)+N(α₁α₃)+...+N(α_n-1α_n-2)+

...+(-1)^n-1 N(α₁α₂α₃ ...α_n-1).                    (3.3)

Subtracting (3.2) from (3.3), we get the formula (3.1) if we note that

N(α'₁α'₂ ...α'_n-1) - N(α'₁α'₂ ...α'_n-1α_n)

= N(α'₁α'₂ ...α'_n-1α'_n).

Thus assuming the principle of inclusion and exclusion for n-1, we have derived if for n.   ?

풀이 . 위의 각 조건을 다음과 같은 벤 다이어그램에 나타내 봅시다.

따라서 위 벤다이어그램에서 확인할 수 있듯이, 어떤 운동도 하지 않는

사람은 5명이다. 또,

n(S) : Sports club 회원 수

n(T) : tennis 하는 회원 수

n(H) : handball 하는 회원 수

n(G) : golf 하는 회원 수

라 두면, 우리가 구하는 수는

n(S) - [n(T)+ n(H) +n(G)- n(T∩H)

- n(T∩G) -n(H∩G)+ n(T∩H∩G)]

이고,   따라서   

       54 - 34 - 22 - 11 + 10 + 6 + 4 - 2 = 5        

이다.    ?

     정수론에 나오는 중요한 함수로    Euler Φ-함수가 있다.

Φ(n) 은 n 보다 작은 자연수 중에서 n 과  서로 소(relative prime)인

수의 개수를 나타낸다.   그리고 Φ(1) = 1 이라고 두자.

그러면 Φ(36) = 12 이다.    실제로  36 보다 작은 수 중에서 36과

서로 소인   수는

         1  5  7  11  13  17  19  23  25  29  31  35

등 모두 12개 이다.

    만일 n 이 서로 다른 소수(prime number) 를   인수로 갖는다면,

우리는 포함배제의 원리에 의하여

을 증명할 수 있다.    (증명은  정수론 책을 참고하시오.)

    예를 들면,  36은  소인수로서   2, 3 이 있으므로

   ?

    많은 간접적인 수 세기의 방법 중에서 가장 기본적이며

 광범위한 응용을 갖는 세기의 방법인 포함배제의 원리와

 그 응용에 대하여 학습하였다.

           45명의 회원이 있는 스포츠 클럽이 있다.

회원 중 30명은 tennis, 28명은 golf를 한다. 이 때,

10명은 tennis와  golf중 어떤 것도 하지 않는다면,

회원 중 tennis와 golf를 모두 다 하는 회원은

모두 몇 명인가 알아보시오.

     많은 간접적인 수 세기의 방법 중에서 가장 기본적이며

 광범위한 응용을 갖는 세기의 방법인 포함배제의 원리의

 응용에 대하여 학습한다.

      포함배제의 원리의 응용

이제 앞에서 학습한 선형 Diophantine 방정식을

해결하는 방법을 알아보도록 합시다.

풀이 .

우리가 구하는 해의 개수는 n ( A^C ∩ B^C ∩ C^C ∩ D^C ) 이다.

 x + y + z + w = 20 을 만족하는 전체 자연수 해의 개수는

임을 알고 있다. 또, 실제로  x' = x - 6 ≥1  이라 두면 준식은

또,  x' , y, z, w 는 모두 자연수인 해를 구하면

이다. 따라서

같은 방법으로,

이다.

따라서 포함배제의 원리 를 적용하면 구하는 해의 개수는

       ?

1부터  n 까지의 숫자를 나열한 permutation  a₁, a₂ ,

...,a_n 중에서 모든 i에 대하여 a_i≠ i인 것을 derrangement

 라고 한다.   

    즉, 231 은 derrangement 이지만, 321은 아니다. 왜냐하면

2 가 제 자리에 있으므로  321은 derrangement 가 아니다.

이제 1부터 n 까지의 숫자를 나열한 derrangement의

개수 Dn 은 얼마인가 구하여 봅시다.

먼저 1부터 n 까지의 permutation의 개수는 모두 n! 임을 알고 있다.

이 때    a_i 를  i 번째  자리에  수자  i 가  오는 permutation들의

집합이라고  하자. 그러면 우리가 구하는 derrangement 의 개수는

이다.    즉,

그러면, 먼저

이므로, 포함배제의 원리에 의하면

-

따라서, 구하는 derrangement의 개수 Dn 은

  

      

이다.    위의 괄호 안의 수는  e- x 의  x = 1 에서의  Taylor전개식과

관련이 있으며, 실제로  n이  무한히 커지면  e^{- 1} 로 수렴함을  알 수

있다.  실제로 작은 n에 대하여도 괄호안의 수자는   0.36788.... 로

  e^{- 1} 에 가까운 수가 된다.

          다음에서   derangement 의 수를 구체적으로 참고하시오.

Derangements. A permutation of n elements in which no element stays in its original position is called a derangement. The solution of the matching game shows that the number Dn of derangements is given by the formula

These numbers are called subfactorials. The following table gives their values for the first 12 natural numbers.: