포함배제의 원리

네 사람이 식당에 모자를 맡겼는데, 직원이 모자를 마구 섞어 아무렇게나 하나씩 돌려주었다. 네 사람 모두 남의 모자를 받을 확률은 얼마일까? 사람이 10명, 100명으로 늘어나면 이 확률은 커질까, 작아질까? 한 사람이라도 제 모자를 받는 경우를 세려 하면, 두 사람이 동시에 받는 경우, 세 사람이 동시에 받는 경우가 겹쳐서 여러 번 세어진다. 겹친 것을 어떻게 정확히 덜어 낼 수 있을까?

1.3.1더하고 빼고 다시 더하다

두 집합의 합집합의 원소 수는 \(n(A) + n(B)\)에서 두 번 세어진 교집합을 한 번 빼서 구한다. 세 집합이면 세 집합의 원소 수를 더하고, 두 집합씩의 교집합을 빼는데, 그러면 세 집합의 공통 부분은 세 번 더해지고 세 번 빠져서 하나도 세어지지 않는다. 그래서 세 집합의 교집합을 다시 한 번 더한다. 이렇게 겹치는 부분을 번갈아 더하고 빼서 각 원소가 정확히 한 번씩 세어지게 하는 것이 포함배제의 원리이다.

완전순열의 식은 포함배제에서 나온다. \(i\)번째 사람이 제 모자를 받는 배열의 집합을 \(A_i\)라 하면, 한 사람 이상이 제 것을 받는 배열의 수는 \(A_1 \cup \cdots \cup A_n\)의 원소 수이다. 특정한 \(k\)명이 제 것을 받는 배열은 나머지 \(n - k\)명을 아무렇게나 늘어놓는 \((n - k)!\)가지이고, \(k\)명을 고르는 방법은 \({}_n\mathrm{C}_k\)가지이므로 \(k\)개씩의 교집합의 합은 \({}_n\mathrm{C}_k(n - k)! = n!/k!\)이다. 이것을 번갈아 더하고 빼 전체 \(n!\)에서 덜어 내면 완전순열의 식이 된다.¹

1.3.2배수의 개수 세기

1부터 100까지의 자연수 가운데 2, 3, 5 가운데 적어도 하나의 배수인 수를 세어 보자. 2의 배수는 50개, 3의 배수는 33개, 5의 배수는 20개이다. 2와 3의 공배수는 6의 배수여서 16개, 3과 5는 15의 배수 6개, 2와 5는 10의 배수 10개이고, 세 수의 공배수는 30의 배수 3개이다. 포함배제로 \(50 + 33 + 20 - 16 - 6 - 10 + 3 = 74\)개이다. 그래서 2, 3, 5 어느 것으로도 나누어떨어지지 않는 수는 26개이다.

1.3.3예제 풀이

그림 2처럼 \(D_4 = 24 - 24 + 12 - 4 + 1 = 9\)이다. 확률은 \(9/24 = 0.375\)이다. 직접 확인하면 네 모자를 모두 제자리가 아니게 놓는 방법은 \(BADC\), \(BCDA\), \(BDAC\), \(CADB\), \(CDAB\), \(CDBA\), \(DABC\), \(DCAB\), \(DCBA\)의 아홉 가지이다.

확률은 \(\dfrac{D_n}{n!} = 1 - 1 + \dfrac{1}{2!} - \dfrac{1}{3!} + \cdots + \dfrac{(-1)^n}{n!}\)이고, 이것은 \(e^{-1}\)의 급수 전개를 \(n\)항까지 더한 것이다. 그래서 사람이 많아지면 확률은 \(1/e \approx 0.3679\)로 다가가고, 다섯 명만 되어도 이미 0.367이다. 확률이 사람 수에 거의 상관이 없는 것이다. 즉 여러 조건이 겹치는 경우를 셀 때는 포함배제의 원리로 겹친 부분을 번갈아 더하고 빼며, 완전순열의 수도 이 방법으로 구한다.

아래 탐구 카드에서 세 집합을 합칠 때 더하고 빼고 다시 더하는 까닭을 확인하고, 모자를 섞어 돌려주는 실험으로 완전순열의 확률을 구해 보자.

1. 이 문제는 1708년 프랑스의 몽모르가 카드 놀이를 분석하며 처음 풀었다. 1부터 13까지 적힌 카드를 섞어 한 장씩 뒤집으며 수를 세었을 때, 카드의 수와 센 수가 한 번도 맞지 않을 확률을 구한 것이다.