3. 포함-배제의 법칙(Inclusion-Exclusion Principle)과 교란순열(Derangement)

포함-배제의 법칙

포함-배제의 법칙(inclusion-exclusion principle)이란 합사건의 확률을 계산하는 데 쓰이는 법칙이다. 2. 확률의 성질 글에서는 두 개짜리 합사건의 확률인 \(P(A\cup B)\)에 관한 포함-배제의 법칙을 유도하였는데, 이는 일반적으로 \(n\)개짜리 합사건에 대해서도 성립하는 식이다. 이를 수식으로 나타내면 다음과 같다.

표본공간 \(\Omega\)의 \(n\)개의 사건 \( E_1, E_2, \cdots, E_n \)에 대하여 $$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^nE_i\right) & = \sum_{i=1}^nP(E_i) \\ & -\sum_{1\leq i<j\leq n}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{n-1}P(E_1\cap E_2\cap\cdots E_n) \end{array} $$

즉 \(n\)개짜리 합사건의 확률을 구하기 위해서는 한 개짜리의 확률은 모두 더하고, 두 개짜리 교집합의 확률은 모두 빼고, 세 개짜리는 모두 더하고… 그런 식으로 번갈아 가면서 더하고 빼면 된다는 게 포함-배제의 법칙이 말해주고 있는 내용이다. 이를 집합의 원소의 개수로 나타내면 다음과 같다.

\(n\)개의 집합 \( A_1, A_2, \cdots, A_n \)에 대하여 $$ \displaystyle\begin{array}{rl} \left|\bigcup_{i=1}^nA_i\right| & = \sum_{i=1}^n|A_i| \\ & -\sum_{1\leq i<j\leq n}|A_i\cap A_j| \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq n}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_j}| \\ & +\cdots+(-1)^{n-1}|A_1\cap A_2\cap\cdots A_n| \end{array} $$

집합의 분배법칙

포함-배제의 법칙을 증명하기 위해서는 분배법칙(distributive property)이라 불리는 집합의 성질에 대해 알아야 한다. 일반적으로 \(n\)개의 집합 \(A_1, A_2, \cdots, A_n\)과 한 집합 \(B\)에 대하여 다음 두 등식을 분배법칙이라고 부른다.

$$ \left(\bigcup_{i=1}^nA_i\right)\cap B=\bigcup_{i=1}^n(A_i\cap B), \qquad \left(\bigcap_{i=1}^nA_i\right)\cup B=\bigcap_{i=1}^n(A_i\cup B) $$

앞의 등식을 풀어 쓰면 아래와 같고, 이는 실수에서 덧셈과 곱셈 사이에서 성립하는 분배법칙과 유사하다.

$$ (A_1\cup A_2\cup\cdots\cup A_n)\cap B=(A_1\cap B)\cup(A_2\cap B)\cup\cdots\cup(A_n\cap B) \\ (a_1+a_2+\cdots+a_n)\times b=(a_1\times b)+(a_2\times b)+\cdots+(a_n\times b) $$

우리가 증명에서 사용할 분배법칙은 위의 두 등식 중 앞의 것이므로, 앞의 것만 증명해 보도록 하자. 뒤의 등식도 똑같은 방식으로 증명 가능하다.

증명

어떤 두 집합이 같음을 보이기 위해서는 보통 서로가 서로에게 포함된다는 것을 보인다. 즉 두 집합 \(X\)와 \(Y\)가 같음을 보이기 위해서 가장 많이 사용하는 방법은 \(X\subseteq Y\)임을 보이고, \(X\supseteq Y\)임을 보이는 것이다. 분배법칙도 이 방법으로 증명할 수 있다.

\(\displaystyle \left(\bigcup_{i=1}^nA_i\right)\cap B\subseteq\bigcup_{i=1}^n(A_i\cap B)\)

\(\displaystyle x\in\left(\bigcup_{i=1}^nA_i\right)\cap B\)라 하자. 그러면 \(\displaystyle x\in\bigcup_{i=1}^nA_i\)이므로 \(n\) 이하의 적당한 자연수 \(k\)에 대하여 \(x\in A_k\)이고, 더불어 \(x\in B\)이다. 따라서 이 자연수 \(k\)에 대하여 \(x\in A_k\cap B\)이고, 따라서 \(\displaystyle x\in\bigcup_{i=1}^n(A_i\cap B)\)이다.

\(\displaystyle \left(\bigcup_{i=1}^nA_i\right)\cap B\supseteq\bigcup_{i=1}^n(A_i\cap B)\)

\(\displaystyle x\in\bigcup_{i=1}^n(A_i\cap B)\)라 하자. 그러면 적당한 자연수 \(k\)에 대해 \(x\in A_k\cap B\)이다. 즉 \(x\in A_k\)이므로 \(\displaystyle x\in\bigcup_{i=1}^nA_i\)이고, 더불어 \(x\in B\)이다. 따라서 \(\displaystyle x\in\left(\bigcup_{i=1}^nA_i\right)\cap B\)이다.

포함-배제의 법칙의 증명

포함-배제의 법칙은 당연히 1. 확률 공리(Axioms of Probability) 글에서 소개했던 확률의 세 가지 공리를 이용해서만 증명이 되어야 하며, 수학적 귀납법을 이용해 증명할 수 있다. 자연수 \(n\)을 사건의 수로 놓고 이 법칙을 \(n\)에 관한 명제 \(p(n)\)으로 놓아 \(p(n)\)이 모든 자연수에 대해 성립한다는 것을 보이려는 것이다. 하지만 2. 확률의 성질 글에서 Bonferroni의 부등식과 Boole의 부등식을 다룰 때와 마찬가지로 이 법칙은 \(n=1\)일 때 너무 당연한 식이 되어 2 이상의 자연수 \(n\)에 대해서 보일 것이고, 따라서 다음과 같은 형태의 귀납법을 사용할 것이다.

  1. (Base Step) \(p(2)\)는 참이다.
  2. (Inductive Step) 2 이상의 자연수 \(k\)에 대해, \(p(k)\)가 참이면 \(p(k+1)\)도 참이다.

Base Step

\(n=2\)일 때 포함-배제 식은 \(P(E_1\cup E_2)=P(E_1)+P(E_2)-P(E_1\cap E_2)\)가 되고, 이는 이전 글에서 살펴보았던 포함-배제의 법칙 식이다. 벤 다이어그램을 그리면 바로 직관적인 증명이 가능하지만, 조금 더 엄밀하게 수식으로 증명해 보도록 하자.

우선 사건 \(E_1\cup E_2\)는 아래 그림과 같이 상호 배타적인 사건 \(E_1\)과 \(E_2\setminus E_1\)으로 나눌 수 있다.

\(E_1\cup E_2\)를 상호 배타적인 사건 \(E_1\)과 \(E_2\setminus E_1\)으로 분해하는 그림. 이로부터 포함-배제의 법칙을 유도할 수 있다.

따라서 3번 공리에 의해

$$ P(E_1\cup E_2)=P(E_1)+P(E_2\setminus E_1) $$

이 된다. 한편 \(E_2\)는 아래 그림과 같이 상호 배타적인 사건 \(E_2\setminus E_1\)과 \(E_2\cap E_1\)으로 나눌 수 있다.

\(E_2\)를 \(E_2\setminus E_1\)과 \(E_2\cap E_1\)의 합집합으로 분해하는 그림. 이로부터 포함-배제의 법칙을 유도할 수 있다.

따라서

$$ P(E_2)=P(E_2\setminus E_1)+P(E_2\cap E_1)\Longrightarrow P(E_2\setminus E_1)=P(E_2)-P(E_1\cap E_2) $$

이고, 이를 위 식에 대입하면 다음을 얻는다.

$$ P(E_1\cup E_2)=P(E_1)+P(E_2)-P(E_1\cap E_2) $$

Inductive Step

이제 2 이상의 자연수 \(k\)에 대해 \(p(k)\)가 성립한다고 하자. 즉

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^kE_i\right) & = \sum_{i=1}^kP(E_i) \\ & -\sum_{1\leq i<j\leq k}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{k-1}P(E_1\cap E_2\cap\cdots E_k) \end{array} $$

이고, 우리는 이를 이용해 \(p(k+1)\), 즉

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^{k+1}E_i\right) & = \sum_{i=1}^{k+1}P(E_i) \\ & -\sum_{1\leq i<j\leq k+1}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k+1}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^kP(E_1\cap E_2\cap\cdots E_{k+1}) \end{array} $$

을 보여야 한다.

우선 \(p(k)\)를 써먹기 위해 \(p(k)\) 식의 좌변과 \(p(k+1)\) 식의 좌변 사이 연결고리를 만들어 줄 것이다. \(\displaystyle\bigcup_{i=1}^{k+1}E_i=\left(\bigcup_{i=1}^kE_i\right)\cup E_{k+1}\)로 쓸 수 있고, 따라서 base step(\(n=2\)일 때 포함-배제의 법칙)에 의해 다음이 성립한다.

$$ P\left(\bigcup_{i=1}^{k+1}E_i\right)=P\left(\left(\bigcup_{i=1}^kE_i\right)\cup E_{k+1}\right)=P\left(\bigcup_{i=1}^kE_i\right)+P(E_{k+1})-P\left(\left(\bigcup_{i=1}^kE_i\right)\cap E_{k+1}\right) $$

여기서 분배법칙을 써 주면 식은 아래와 같이 변한다.

$$ P\left(\bigcup_{i=1}^{k+1}E_i\right)=P\left(\bigcup_{i=1}^kE_i\right)+P(E_{k+1})-P\left(\bigcup_{i=1}^k(E_i\cap E_{k+1})\right) $$

우변에서 첫 번째와 세 번째 항은 모두 \(k\)개짜리 합집합의 확률이므로 여기에 \(p(k)\)가 성립한다는 가정을 써먹을 수 있다. 그러면 다음 두 식이 성립한다.

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^kE_i\right) & = \sum_{i=1}^kP(E_i) \\ & -\sum_{1\leq i<j\leq k}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{k-1}P(E_1\cap E_2\cap\cdots E_k) \end{array} $$

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^k(E_i\cap E_{k+1})\right) & = \sum_{i=1}^kP(E_i\cap E_{k+1}) \\ & -\sum_{1\leq i<j\leq k}P(E_i\cap E_j\cap E_{k+1}) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}\cap E_{k+1}) \\ & +\cdots+(-1)^{k-1}P(E_1\cap E_2\cap\cdots E_k\cap E_{k+1}) \end{array} $$

위에서부터 차례대로 1번, 2번 식이라고 하자. 이제 이들을 대입해줄 건데… 무작정 대입하기보다는 대입했을 때 식과 아래 식의 우변을 비교해 보자. 포함-배제의 법칙이 성립한다면 이 둘은 같아야 할 것이다.

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^{k+1}E_i\right) & = \sum_{i=1}^{k+1}P(E_i) \\ & -\sum_{1\leq i<j\leq k+1}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq k+1}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^kP(E_1\cap E_2\cap\cdots E_{k+1}) \end{array} $$

위 식의 우변에는 집합 한 개짜리 확률부터 \(k+1\)개짜리 교집합들의 확률까지, 총 \(k+1\)종류가 있다. 이들이 모두 있는지, 부호(\(\pm\))가 모두 맞는지 살펴보자.

  • 1개짜리 확률은 모두 있다. \(P(E_1)\)부터 \(P(E_k)\)까지는 1번 식에, \(P(E_{k+1})\)은 원래 식에 있다. 부호는 모두 (+)로 맞는 것을 볼 수 있다.
  • 2개짜리 교집합들의 확률도 모두 있다. \(P(E_1\cap E_2)\) 등 \(E_{k+1}\)이 들어가지 않은 것들은 1번 식에 (-) 부호로, \(P(E_1\cap E_{k+1})\) 등 \(E_{k+1}\)이 들어간 것들은 2번 식에 (+) 부호로 있다. 2번 식은 원래 식에 대입되며 부호가 바뀌므로, 결국에는 모두 (-)로 맞게 된다.
  • 3개짜리 교집합들의 확률도 모두 있다. \(E_{k+1}\)이 들어가지 않은 것들은 1번 식에, \(E_{k+1}\)이 들어간 것들은 2번 식에 있다. 마찬가지로 부호도 모두 맞다.
  • \(k\)개짜리 교집합들의 확률도 모두 있다. \(E_{k+1}\)이 들어가지 않은 것들은 1번 식에, \(E_{k+1}\)이 들어간 것들은 2번 식에 있다. 부호도 모두 맞다.
  • 마지막으로, \(k+1\)개짜리 교집합들의 확률도 있다. 부호도 맞다.

따라서 \(p(k+1)\)이 성립한다.

교란순열

문제 소개

지금까지 포함-배제의 법칙을 소개하고 복잡하고 긴 과정을 거쳐서 증명해 보았다. 이제 이 법칙을 이용하여 풀 수 있는 유명한 문제를 하나 풀면서 글을 마무리하려고 한다.

\(n\)명의 사람들이 커다란 공터에 자신의 가방을 하나씩 던져 놓은 후 \(n\)개의 가방 중 아무거나 하나를 골라 다시 맨다. 이때 아무도 자신의 가방을 매지 않을 확률(경우의 수)은?

위 조건을 만족하는 경우의 수를 교란순열(derangement)이라고 하고, 보통 \(D_n\)으로 나타낸다. 예를 들어, \(n=3\), 사람들을 \(A, B, C\)라고 하면 아래 표와 같은 두 가지 경우가 가능하고, 전체 경우의 수는 \(3!=6\)이므로 구하는 확률은 \(\displaystyle\frac{2}{6}=\frac{1}{3}\)이다.

A B C
B의 가방 C의 가방 A의 가방
C의 가방 A의 가방 B의 가방

아이디어

일반적인 순열/조합의 공식을 사용해서는 문제가 쉽게 풀리지 않을 것이고, 단순히 수형도를 그려서 구하기에는 \(n\)이 조금만 커져도 경우의 수가 너무 많아진다. 이 문제는 포함과 배제 법칙을 이용하여 풀 수 있고, 그 아이디어는 다음과 같다.

\(n\)명의 사람들을 \(A_1, A_2, \cdots, A_n\)이라고 하고, 사람 \(A_i\)가 자신의 가방을 매는 사건을 \(E_i\)라고 하자. 그러면 \(A_i\)가 자신의 가방을 매지 않는 사건은 \(E_i^C\)가 되고, 구하는 확률은 모두가 자신의 가방을 매지 않을 확률이므로, 이를 \(P_n\)이라 하면

$$ P_n=P\left(\bigcap_{i=1}^nE_i^C\right) $$

이다. 이때 드 모르간의 법칙에 의해 \(\displaystyle\bigcap_{i=1}^nE_i^C=\left(\bigcup_{i=1}^nE_i\right)^C\)가 되고, 2. 확률의 성질 글에서 나온 성질(여사의 확률)에 의해

$$ P_n=P\left(\left(\bigcup_{i=1}^nE_i\right)^C\right)=1-P\left(\bigcup_{i=1}^nE_i\right) $$

이다. 이때 포함-배제의 법칙에 의해

$$ \displaystyle\begin{array}{rl} P\left(\bigcup_{i=1}^nE_i\right) & = \sum_{i=1}^nP(E_i) \\ & -\sum_{1\leq i<j\leq n}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{n-1}P(E_1\cap E_2\cap\cdots E_n) \end{array} $$

이고, \(P(E_i)\), \(P(E_i\cap E_j)\), \(P(E_i\cap E_j\cap E_k)\)등은 쉽게 구할 수 있고, 이들을 계산한 후 대입하면 구하는 확률이 나온다.

풀이

\(n\)명의 사람들을 \(A_1, A_2, \cdots, A_n\)이라고 하고, 사람 \(A_i\)가 자신의 가방을 매는 사건을 \(E_i\)라고 하자. 그러면 포함-배제의 법칙에 의해 구하는 확률은

$$ \begin{array}{rl} P_n & =P\left(\bigcap_{i=1}^nE_i^C\right) \\ & =1-P\left(\bigcup_{i=1}^nE_i\right) \\ & =1-[\sum_{i=1}^nP(E_i) \\ & -\sum_{1\leq i<j\leq n}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{n-1}P(E_1\cap E_2\cap\cdots E_n)] \end{array} $$

이다. 이제 사건 한 개짜리 확률, 두 개짜리 교집합의 확률부터 \(n\)개짜리 교집합의 확률까지를 모두 구해보자.

  • \(P(E_i)\)는 다른 사람들은 상관없이 사람 \(A_i\)가 자신의 가방을 맬 확률이다. \(A_i\)는 \(n\)개의 가방 중 아무거나 하나를 모두 같은 확률로 가져가므로 \(\displaystyle P(E_i)=\frac{1}{n}\)이다.
  • \(P(E_i\cap E_j)\)는 마찬가지로 다른 사람들은 상관없이 \(A_i\)와 \(A_j\)가 자신의 가방을 맬 확률이다. \(A_i\)는 \(n\)개의 가방 중 아무거나 하나를, \(A_j\)는 나머지 \((n-1)\)개의 가방 중 아무거나 하나를 모두 같은 확률로 가져가므로 \(\displaystyle P(E_i\cap E_j)=\frac{1}{n(n-1)}\)이다.
  • 같은 맥락으로 \(\displaystyle P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j})=\frac{1}{n(n-1)\cdots(n-j+1)}\)이다. 이때 분모는 \(n\)부터 1씩 내려가면서 총 \(j\)개를 곱한 것이다.
  • 마지막으로 \(\displaystyle P(E_1\cap E_2\cap\cdots E_n)=\frac{1}{n(n-1)\cdots\cdot1}\)이다.

정리하자면, \(j(1\leq j\leq n)\)개짜리 교집합의 확률은

$$ \frac{1}{n(n-1)\cdots(n-j+1)}=\frac{(n-j)(n-j-1)\cdots\cdot1}{n(n-1)\cdots\cdot1}=\frac{(n-j)!}{n!} $$

이다. 이제 이들을 원래 식에 집어넣어 줄 건데, 포함-배제의 법칙 식의 \(j\)번째 시그마 기호

$$ \sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) $$

에 포함된 \(j\)개짜리 교집합은

$$ \begin{pmatrix} n \\ j \end{pmatrix}=\frac{n!}{j!(n-j)!} $$

개이다. 따라서 이 \(j\)번째 시그마 기호를 계산한 결과는

$$ \sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j})=\frac{(n-j)!}{n!}\times\frac{n!}{j!(n-j)!}=\frac{1}{j!} $$

이고, 구하는 확률은

$$ \begin{array}{rl} P_n & =1-P\left(\bigcup_{i=1}^nE_i\right) \\ & =1-[\sum_{i=1}^nP(E_i) \\ & -\sum_{1\leq i<j\leq n}P(E_i\cap E_j) \\ & +\cdots \\ & +(-1)^{j-1}\sum_{1\leq i_1<i_2<\cdots<i_j\leq n}P(E_{i_1}\cap E_{i_2}\cap\cdots\cap E_{i_j}) \\ & +\cdots+(-1)^{n-1}P(E_1\cap E_2\cap\cdots E_n)] \\ & = 1-\left(\frac{1}{1!}-\frac{1}{2!}+\frac{1}{3!}-\cdots+\frac{(-1)^{n-1}}{n!}\right) \\ & =\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\cdots+\frac{(-1)^n}{n!} \\ & =\sum_{i=0}^n\frac{(-1)^i}{i!} \end{array} $$

이다.

참고사항

  1. \(P_n\)에 \(n\)개로 만들 수 있는 모든 순열의 수인 \(n!\)을 곱하면 교란순열 \(D_n\)이 나온다. $$ D_n=n!P_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!} $$ \(n=1\)일 때부터 5일 때까지 \(D_n\)의 값은 0, 1, 2, 9, 44이다.
  2. 사람 수 \(n\)이 많아질수록 확률 \(P_n\)은 어떤 값에 가까워질까? \(e^x\)의 테일러 급수 $$ e^x=\sum_{i=0}^\infty\frac{x^i}{i!} $$에 의해 구하는 확률은 $$ \lim_{n\rightarrow\infty}P_n=\sum_{i=0}^\infty\frac{(-1)^i}{i!}=\frac{1}{e}\approx0.3679 $$이다.

Leave a Comment