포함배제의 원리

• 포함배제의 원리(확률의 경우)
  • 포함배제의 원리 증명

- 수통 과제에 포함배제의 원리 증명이 있는데 헷갈려서 따로 정리함

포함배제의 원리(확률의 경우)

- 임의의 유한개의 사건 $A_1, \cdots, A_k \in S$ 에 대하여 아래가 성립함

• $P\Big(\bigcup\limits^{K}_{i=1}A_i\Big) = \sum\limits_{i=1}^{k}P(A_i) - \sum\limits_{1\leq i < j \leq k}^{k}P(A_i\cap A_j) +\cdots+(-1)^{k-1}P\Big(\bigcap\limits_{i=1}^{k}A_i\Big)$

- 이제 증명을 해보자 ---> 수학적 귀납법을 활용할 것 임

- $n = 1$일 때 식이 성립함을 증명 ---> $n=k$일 때 성립한다 가정하고 $n=k+1$일 때 식이 성립함을 증명

- $n=k$일 때 성립하면 $n=k+1$일 때도 성립한다고 했음 ---> $n = 1$일 때 성립하면 $n=2$일 때도 성립 ---> $n = 1$일 때 식이 성립함 ---> $n=2$일 때 식이 성립

- 이제 $n=2$일 때 성립하면 $n=3$일 때도 성립 ---> $n = 2$일 때 식이 성립함 ---> $n=3$일 때 식이 성립

- 이런식으로 나아가면 모든 자연수에 대해서 성립함을 알 수 있음

- $n=1$대신 $n=a$로 바뀐다면 $a$이후의 자연수에 대해서 성립함을 알 수 있음

포함배제의 원리 증명

- $A\cap B = C \to C \cap A = C,\; C \cap B = C,C \cup A = A,\; C \cup B = B$ ---> 당연하지만 알아두자

- $n=1$일 때 $P(A_1) = P(A_1)$이므로 성립함

- 이제 $n=k$일 때 성립한다 가정하고 $n=k+1$일 때 성립하는지 살펴보자

• $P\bigg(\bigcup\limits_{i=1}^{k+1}A_i \bigg) = P\bigg(\bigg(\bigcup\limits_{i=1}^{k}A_i\bigg)\bigcup A_{k+1}\bigg) \quad\therefore \text{나열해서 보면 당연한 소리}\\ = P\bigg(\bigcup\limits_{i=1}^{k}A_i\bigg) + P(A_{k+1}) - P\bigg(\bigg(\bigcup\limits_{i=1}^{k}A_i \bigg)\bigcap A_{k+1}\bigg)\\ \therefore P(X\cup Y) = P(X)+P(Y)-P(X\cap Y),\quad X\to \bigcup\limits^k_{i=1}A_i,\;Y \to A_{k+1}\\ =P\bigg(\bigcup\limits_{i=1}^{k}A_i\bigg) + P(A_{k+1}) - P\bigg(\bigcup\limits_{i=1}^{k}\big(A_i \cap A_{k+1}\big)\bigg)\\ \therefore\text{집합의 분배법칙,}\; P\bigg(\bigcup\limits_{i=1}^{k} X_i \bigg) = \sum\limits_{i=1}^{k}P(X_i) - \sum\limits_{1\leq i < j \leq k}^{k}P(X_i\cap X_j) +\cdots+(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}X_i\bigg)\\ = \bigg\{\sum\limits_{i=1}^{k}P(A_i) - \sum\limits_{1\leq i < j \leq k}^{k}P(A_i\cap A_j) +\cdots+(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}A_i\bigg)\bigg\} +P(A_{k+1})-\bigg\{\sum\limits_{i=1}^{k}P(A_i\cap A_{k+1}) - \sum\limits_{1\leq i < j \leq k}^{k}P((A_i\cap A_{k+1})\cap A_j) +\cdots+(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}(A_i \cap A_{k+1})\bigg)\bigg\}\\ = \sum\limits_{i=1}^{k}P(A_i) - \sum\limits_{1\leq i < j \leq k}^{k}P(A_i\cap A_j) +\cdots+(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}A_i\bigg) +P(A_{k+1})-\sum\limits_{i=1}^{k}P(A_i\cap A_{k+1}) + \sum\limits_{1\leq i < j \leq k}^{k}P((A_i\cap A_{k+1})\cap A_j) -\cdots+(-1)^{k+1-1}P\bigg(\bigcap\limits_{i=1}^{k+1}A_i\bigg)\\ \therefore-\,(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}(A_i\cap A_{k+1})\bigg) = (-1)^{k+1-1}P\bigg(\bigcap\limits_{i=1}^{k+1}A_i\bigg)\\ = \sum\limits_{i=1}^{k+1}P(A_i) - \sum\limits_{1\leq i < j \leq k+1}^{k+1}P(A_i\cap A_j) +\cdots+(-1)^{k+1-1}P\bigg(\bigcap\limits_{i=1}^{k+1}A_i\bigg)\\ \therefore\text{그러므로 $n=k+1$일 때도 성립한다}$

- 마지막 부분이 이해가 안될 수 도 있음

- 일단 $\sum\limits_{i=1}^{k}P(A_i)$ 와 $P(A_{k+1})$를 더해서 $\sum\limits_{i=1}^{k+1}P(A_i)$가 되는것은 알 것임

- 그건 맞다고 치자 ---> 그 다음부터는 뭐임??

- $- \sum\limits_{1\leq i < j \leq k+1}^{k+1}P(A_i\cap A_j)$ ---> 이건 어떻게 도출됨??

- 아래식을 보자

- $ - \sum\limits_{1\leq i < j \leq k}^{k}P(A_i\cap A_j)-\sum\limits_{i=1}^{k}P(A_i\cap A_{k+1}) = - \sum\limits_{1\leq i < j \leq k+1}^{k+1}P(A_i\cap A_j)$

- 위 식이 성립하는 것만 이해하면 전부다 이해 가능 ---> 왜 성립함? ---> 그냥 나열해보면 성립하는 것을 알 수 있음 ---> 설명을 더 해보자

- $P\bigg(\bigcup\limits^{K}_{i=1}A_i\bigg)$에서 $P\bigg(\bigcup\limits^{K+1}_{i=1}A_i\bigg)$로 업그레이드(?)시킬 수 있다는 것은 $n=k$가 성립하면 $n=k+1$일 때 도 성립한다는 뜻

- 잘보면 왼쪽식에서 오른쪽식으로 나아가기 위해서는 사건$A_{k+1}$과 연관된 식이 있어야 함

- 예컨데 $k=3$이라고 해보자

- $\sum\limits_{1\leq i < j \leq 3}^{3}P(A_i\cap A_j)=P(A_1\cap A_2)+P(A_1\cap A_3)+P(A_2\cap A_3) \;\cdots\text{식 (1)}$

- 여기서 $k$대신 $k+1$을 넣어보자

- $\sum\limits_{1\leq i < j \leq 3+1}^{3+1}P(A_i\cap A_j)=P(A_1\cap A_2)+P(A_1\cap A_3)+P(A_1\cap A_4)+P(A_2\cap A_3)+P(A_2\cap A_4)+P(A_3\cap A_4)$

- 즉 우리에겐 $n=k$일 때는 존재하지 않는 사건 $A_{k+1}$과 연관된 식인 $P(A_1\cap A_4)+P(A_2\cap A_4)+P(A_3\cap A_4)\;\cdots\text{식 (2)}$가 있어야 $n=k+1$일 때의 식으로 나아갈 수 있음 ---> 이 식이 바로 $-\sum\limits_{i=1}^{k}P(A_i\cap A_{k+1})$

- 식 (1)과 식 (2)가 합쳐져서 $n=k+1$일 때의 식을 만들어 내는 것임

- $\sum\limits_{i=1}^{k}P(A_i) - \sum\limits_{1\leq i < j \leq k}^{k}P(A_i\cap A_j) +\cdots+(-1)^{k-1}P\bigg(\bigcap\limits_{i=1}^{k}A_i\bigg)$ ---> 식 (1)의 역할, $P(A_{k+1})-\sum\limits_{i=1}^{k}P(A_i\cap A_{k+1}) + \sum\limits_{1\leq i < j \leq k}^{k}P((A_i\cap A_{k+1})\cap A_j) -\cdots+(-1)^{k+1-1}P\bigg(\bigcap\limits_{i=1}^{k+1}A_i\bigg)$ ---> 식 (2)의 역할

- 위의 두 식($n\leq k$까지의 정보와 $n=k+1$일 때의 정보)이 합쳐져서 $P\bigg(\bigcup\limits^{K+1}_{i=1}A_i\bigg)=\sum\limits_{i=1}^{k+1}P(A_i) - \sum\limits_{1\leq i < j \leq k+1}^{k+1}P(A_i\cap A_j) +\cdots+(-1)^{k+1-1}P\bigg(\bigcap\limits_{i=1}^{k+1}A_i\bigg)$ ($n \leq k$까지의 정보)가 되는 것임