확률론 : 1.1. 경우의 수와 이항정리

1. 확률론 기초

확률론에 대한 기초적인 개념들에 대해 설명해봅니다. 흔히 고등학교 교과과정에서 하는 식으로, 경우의 수와 이항정리에 대해 먼저 다룹니다. 그 다음으로는 확률에 대하여 직관적인 방식과 엄밀한 방식으로 각각 설명해봅니다. 이후에는 조건부확률과 독립사건의 개념을 배운 후 Sterling’s lemma에 대해 간략히 살펴봅니다.

1.1. 경우의 수와 이항정리

(1) 순열 (permutation)

서로 다른 $n$개의 대상을 일렬로 나열하는 방법의 수는

\[n!=n\times(n-1)\times\cdots\times1\]

입니다. $n!$은 ‘n 팩토리얼(factorial)’이라고 읽고, $0!=1$로 정의합니다.

서로 다른 $n$개의 대상 중 $r$개를 일렬로 나열하는 방법의 수는

\[_nP_r=\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)\]

입니다.

예를 들어, 5개의 서로 다른 구슬들을 일렬로 나열하는 방법의 수는

\[5!=5\times4\times3\times2\times1=120\]

로부터 120가지입니다. 또한, 5개의 서로 다른 구슬들 중 2개를 뽑아 일렬로 나열하는 방법의 수는

\[_5P_2=5\times4=20\]

으로부터 20가지입니다.

또 다른 예를 들면, 집합 $X=\{1,2,3,4\}$에 대하여 $X$를 정의역과 공역으로 갖는 일대일 대응 함수 $f$의 개수는 $4!=24$개 입니다. 일대일 대응 함수 $f$를 정하려면 함숫값 $f(1)$, $f(2)$, $f(3)$, $f(4)$를 차례로 정하면 되는데 각각의 함숫값은 1, 2, 3, 4 중에서 정할 수 있고, 중복되면 안되므로 $4\times3\times2\times1$와 같이 계산하는 것입니다.

참고
그런 의미에서인지, 일반적으로 유한집합 $X$에 대하여 $X$에서 $X$로 가는 일대일대응 함수를 'permutation'이라고 부릅니다.

(2) 같은 것이 포함된 순열

세 종류의 대상 $A$, $B$, $C$가 각각 $a$개, $b$개, $c$개 있을 때($a+b+c=n$), 이 $n$개의 대상을 일렬로 나열하는 방법의 수는

\[\frac{n!}{a!b!c!}\]

입니다.

예를 들어, 2개의 빨간 구슬과 2개의 노란 구슬, 그리고 1개의 파란 구슬이 있을 때, 이 다섯 개의 구슬을 일렬로 나열하는 방법의 수는

\[\frac{5!}{2!2!1!}=30\]

으로부터 30가지입니다. 왜냐하면, 단순히 다섯 개의 구슬을 나열하는 방법은 $5!=120$개 이지만, 빨간 구슬 두 개는 서로 같은 구슬이므로 $2!$개만큼 중복되었고, 마찬가지로 파란 구슬 두 개는 서로 같은 구슬이므로 $2!$개만큼 중복되었으므로 중복된 횟수만큼 나누어주어야 하기 때문입니다.

꼭 세 종류의 대상이 아니라 여러 종류의 대상이더라도 같은 방식의 계산이 적용됩니다. $k$ 종류의 대상 $A_1$, $A_2$, $\cdots$, $A_k$가 각각 $n_1$, $n_2$, $\cdots$, $n_k$개 있을 때 ($n_1+n_2+\cdots+n_k=n$), 이 $n$개의 대상을 일렬로 나열하는 방법의 수는

\[\frac{n!}{n_1!n_2!\cdots n_k!}\]

입니다. 예를 들어, 10개의 알파벳으로 이루어진 단어 “statistics”를 다시 배열해 만들 수 있는 새로운 단어의 개수는

\[\frac{10!}{3!3!2!1!1!}=50400\]

으로부터 50400개 입니다.

(3) 조합 (combination)

서로 다른 $n$개의 대상들 중 $r$개를 선택하는 방법의 수는

\[\binom nr=\frac{_nP_r}{r!}=\frac{n!}{r!(n-r)!}\]

입니다. 이때, 중복을 허용하지 않고 뽑습니다. 중복을 허용하여 뽑는 경우는 중복조합이라고 불리며, 조금 다른 계산법이 적용됩니다.

예를 들어, 5개의 서로 다른 구슬들 중 2개를 뽑는 방법의 수는

\[\binom52=\frac{_5P_2}{2!}=\frac{20}2=10\]

으로부터 10가지입니다.

(4) 순열 vs 조합

위 문제를 앞서 배운 개념들과 연관지어서 생각해보면 다음과 같습니다.

5개의 서로 다른 구슬을 $A$, $B$, $C$, $D$, $E$라고 하겠습니다. 5개의 구슬을 (중복을 허용하여) 차례대로 2개 뽑아 나열하는 전체 경우의 수는 $5\times4=25$개입니다. (중복순열, $_5\Pi_2$)

$(A,A)$	$(A,B)$	$(A,C)$	$(A,D)$	$(A,E)$
$(B,A)$	$(B,B)$	$(B,C)$	$(B,D)$	$(B,E)$
$(C,A)$	$(C,B)$	$(C,C)$	$(C,D)$	$(C,E)$
$(D,A)$	$(D,B)$	$(D,C)$	$(D,D)$	$(D,E)$
$(E,A)$	$(E,B)$	$(E,C)$	$(E,D)$	$(E,E)$

그러나 위에 배웠던 순열의 개념은 구슬 2개를 뽑아 나열하는 것이므로, 두 구슬이 중복되면 안됩니다. 이 경우의 경우의 수는 $5\times4=20$개 입니다. (순열, $_5P_2$)

	$(A,B)$	$(A,C)$	$(A,D)$	$(A,E)$
$(B,A)$		$(B,C)$	$(B,D)$	$(B,E)$
$(C,A)$	$(C,B)$		$(C,D)$	$(C,E)$
$(D,A)$	$(D,B)$	$(D,C)$		$(D,E)$
$(E,A)$	$(E,B)$	$(E,C)$	$(E,D)$

또한, 조합의 개념은 두 개를 뽑기만 할 뿐 나열하지는 않습니다. 즉, $(A,B)$와 $(B,A)$를 같은 것으로 봅니다. 계산은 $\frac{5\times4}2=10$개 와 같이 됩니다. (조합, $_5C_2=\binom52$)

	$(A,B)$	$(A,C)$	$(A,D)$	$(A,E)$
		$(B,C)$	$(B,D)$	$(B,E)$
			$(C,D)$	$(C,E)$
				$(D,E)$

2개를 뽑되 중복을 허용하여 뽑는 경우도 있습니다. 아래 그림에서 총 15개의 경우가 나타납니다. (중복조합, $_5H_2$)

$(A,A)$	$(A,B)$	$(A,C)$	$(A,D)$	$(A,E)$
	$(B,B)$	$(B,C)$	$(B,D)$	$(B,E)$
		$(C,C)$	$(C,D)$	$(C,E)$
			$(D,D)$	$(D,E)$
				$(E,E)$

(5) 같은 것이 포함된 순열 vs 조합

$A$, $B$, $C$, $D$, $E$ 중에 두 개를 뽑는 것은, 다섯 개의 숫자 $1$, $1$, $0$, $0$, $0$을 일렬로 나열하는 것과 정확히 대응됩니다. 예를 들어 숫자를 $11000$으로 나열했으면, 첫번째 알파벳과 두번째 알파벳을 뽑는 것($A$, $B$)으로 해석하고, $01001$으로 나열했으면 두번째 알파벳과 다섯번째 알파벳을 뽑는 것($B$, $E$)으로 해석하는 것입니다. 다섯 개의 숫자 $1$, $1$, $0$, $0$, $0$를 일렬로 나열하는 방법의 수는

\[\frac{5!}{2!3!}=10\]

으로부터 10개이므로, $\binom52$의 값과 일치하는 것을 확인할 수 있습니다. 즉, 조합의 개념을 같은 것이 포함된 순열의 특별한 경우로 해석할 수 있습니다.

(6) 이항정리

중고등학교에서 수학에서 (각각 중3, 고1 과정) 다음과 같은 곱셈공식을 공부합니다.

\[\begin{align*} (a+b)^2&=a^2+2ab+b^2\\ (a+b)^3&=a^3+3a^2b+3ab^2+b^3 \end{align*}\]

이때 위의 식들을

\[\begin{align*} (a+b)^2&=\binom20a^2+\binom21ab+\binom22b^2\\ (a+b)^3&=\binom30a^3+\binom31a^2b+\binom32ab^2+\binom33b^3 \end{align*}\]

와 같이 쓸 수 있습니다. (아래의 조합의 값들을 계산해보면 정확히 위의 식의 계수들과 일치합니다.) 이것은 우연의 일치가 아닙니다. 예를 들어, 두번째 전개식에서 $a^2b$의 계수가 $\binom31$이 되는 이유는 다음과 같습니다. $(a+b)^3$을 전개했을 때 $a^2b$가 나오는 횟수는, 세 개의 알파벳 $a$, $a$, $b$를 일렬로 나열하는 경우의 수와 같습니다. 그 경우의 수는 (같은 것이 포함된 순열에 의해) $\frac{3!}{2!1!}$와 같이 계산될 수 있고, 이것은 다시 $\binom31$로 계산될 수도 있는 것입니다.

따라서, 위의 식들을 일반화할 수 있습니다. 이것을 이항정리라고 합니다.

이항정리(biomial theorem)
두 실수 $a$, $b$와 자연수 $n$에 대하여 다음 식이 성립합니다. $$ \begin{align*} (a+b)^n &=\binom n0a^n+\binom n1a^{n-1}b+\cdots+\binom nnb^n\\ &=\sum_{r=1}^n\binom nra^rb^{n-r} \end{align*} $$

즉, 식 $(a+b)^n$을 전개할 때 $a^rb^{n-r}$항의 개수는 $r$개의 $a$와 $n-r$개의 $b$를 일렬로 배열하는 방법의 수인 $\binom nr$와 같습니다. 두 개의 항으로 이루어진 식을 거듭제곱할 때 나타나는 모양을 다루고 있으므로 ‘이항정리’라는 이름이 붙었습니다. 이때, $\binom nr$는 두 개의 항으로 이루어진 식을 거듭제곱할 때, 각 항의 계수이므로 이항계수(binomial coefficient)라고도 불립니다.

이항정리로부터 얻을 수 있는 간단한 식들은 다음과 같습니다. 각각, $(a,b)=(1,1)$, $(a,b)=(-1,1)$을 대입하여 얻을 수 있는 결과입니다.

\[\begin{align*} \sum_{k=1}^n\binom nk&=2^n\\ \sum_{k=1}^n(-1)^k\binom nk&=0 \end{align*}\]

예를 들어,

\[\begin{align*} \binom40+\binom41+\binom42+\binom43+\binom44&=16\\[10pt] \binom40-\binom41+\binom42-\binom43+\binom44&=0\\[10pt] \binom50+\binom51+\binom52+\binom53+\binom54+\binom55&=32\\[10pt] \binom50-\binom51+\binom52-\binom53+\binom54-\binom55&=0 \end{align*}\]

입니다. 이 식들을 적당히 연립하면

\[\begin{align*} \binom40+\binom42+\binom44 &=8\\[10pt] \binom41+\binom43 &=8\\[10pt] \binom50+\binom52+\binom54&=16\\[10pt] \binom51+\binom53+\binom55&=16 \end{align*}\]

와 같은 결과를 얻을 수도 있습니다.

참고
이항정리는 $a$와 $b$가 복소수일 때도 성립합니다. 일반적으로, $a$와 $b$가 어떤 field의 원소이면 이항정리가 성립합니다. 조금 더 일반적으로는, $a$와 $b$가 commutative ring의 원소여도 이항정리가 성립할 것입니다.

(7) 이항계수의 성질

이번 파트에서는 이항계수(혹은 조합)의 두 가지 성질에 대해 살펴봅니다. 이 성질들은 나중에 이항분포의 기댓값과 분산을 계산할 때 쓰입니다.

이항계수의 성질 - 1
$1\le r\lt n$을 만족시키는 정수 $n$, $r$에 대하여 다음 식이 성립합니다. $$ \binom nr+\binom n{r+1}=\binom{n+1}{r+1} $$

증명 :

\[\begin{align*} \binom nr+\binom n{r+1} &=\frac{n!}{r!(n-r)!}+\frac{n!}{(r+1)!(n-r-1)!}\\ &=\frac{n!\times(r+1)}{r!(n-r)!\times(r+1)}+\frac{n!\times(n-r)}{(r+1)!(n-r-1)!\times(n-r)}\\ &=(r+1)\times\frac{n!}{(r+1)!(n-r)!}+(n-r)\times\frac{n!}{(r+1)!(n-r)!}\\ &=\left((r+1)+(n-r)\right)\times\frac{n!}{(r+1)!(n-r)!}\\ &=(n+1)\times\frac{n!}{(r+1)!(n-r)!}\\ &=\frac{(n+1)!}{(r+1)!\left((n+1)-(r+1)\right)!}\\ &=\binom{n+1}{r+1}. \end{align*}\]

이항계수의 성질 - 2
$1\lt r\le n$을 만족시키는 정수 $n$, $r$에 대하여 다음 식이 성립합니다. $$ r\times\binom nr=n\times\binom{n-1}{r-1} $$

증명 :

\[\begin{align*} r\times\binom nr &=r\times\frac{n!}{r!(n-r)!}\\ &=\frac{n!}{(r-1)!(n-r)!}\\ &=n\times\frac{(n-1)!}{(r-1)!\left((n-1)-(r-1)\right)!}\\ &=n\times\binom{n-1}{r-1} \end{align*}\]