[수리통계학] 1. 표본공간과 사건, 순열과 조합, 이항계수

1. 표본공간과 사건, 순열과 조합, 이항계수

실험 또는 관측하는 행위를 시행(trial 또는 experiment)이라 하고, 시행의 결과를 확실히 예측하기 어려운 실험(예측불가능한 시행)을 무작위 시행(random trial)이라고 한다. 시행으로 얻어진 결과들의 집합을 표본공간(sample space)이라 하고, 이를 $S$로 나타낸다.

표본공간의 원소가 유한개이거나 자연수 $\mathbb{N}$에 일대일로 대응시킬 수 있으면, 이 표본공간은 셀 수 있다(countable)고 한다.  

표본공간의 부분집합을 사건(event)이라 하고, 이를 $A,\,B,\,C,\,\cdots$로 나타낸다.

사건의 기본연산:

$A$와 $B$의 합사건: $A\cup B$

$A$와 $B$의 곱사건: $A\cap B$

$A$의 여사건: $A^{c}$

$A\cap B=\emptyset$인 사건 $A$, $B$를 상호배타(mutually exclusive)적(또는 배반사건)이라고 한다.

 

두가지 시행이 있을 때, 첫번째 시행에서 $m$가지의 결과가 있고, 두번째 시행에서 $n$가지의 결과가 있을 때, 첫번째 시행을 하고 이어서 두번째 시행을 하는 시행의 결과는 $mn$가지 이다.

$n$개의 다른 개체들 중에서 중복을 허용해서 $k$개를 선택하는 경우의 수는 $n^{k}$이다.(중복순열)

$n$개의 다른 개체들을 일렬로 나열하는 경우의 수는 $$n!=n(n-1)\cdots3\cdot2\cdot1$$ 이고, 여기서 $0!=1$로 정의한다. 

$n$개의 다른 개체들 중에서 $k$개를 선택하는 경우의 수는 $$_{n}P_{k}=n(n-1)\cdots(n-k-1)=\frac{n!}{(n-k)!}$$ (순열, permutation)이고, 순서를 고려하지 않고, $k$개를 선택하는 경우의 수는 $$\binom{n}{k}=\frac{_{n}P_{k}}{k!}=\frac{n!}{k!(n-k)!}$$ (조합, combination)이다.

문자 abc의 가능한 배열은 abc, acb, bac, bca, cab, cba의 6가지이고, $3!=3\cdot2\cdot1=6$이다.

문자 abcd중에서 2개를 선택하는 경우의 수는 $_{4}P_{2}=4\cdot3=12$이다.

어느 대학에 소속된 수학교수 6명과 물리교수 7명중에서 3명의 수학교수와 4명의 물리교수로 대입논술시험 출제진을 구성할 때의 가짓수는 $$\binom{6}{3}\binom{7}{4}=\frac{6!}{3!3!}\frac{7!}{4!3!}=20\cdot35=700$$ 이다.

 

$n$명이 원탁에 앉는 경우의 수는 $(n-1)!$이다.

증명:

(i) $n$가지의 같은 경우가 나타나므로 $\displaystyle\frac{n!}{n}=(n-1)!$이다.

(ii) 한 사람을 고정하고, 나머지 $n-1$명에 대해 배열하면 되므로 $(n-1)!$이다.

$n$개의 서로 다른 원소로 구성된 집합에서 첫번째 부분집합에 $n_{1}$개의 원소, 두번째 부분집합에는 $n_{2}$개의 원소, ..., $k$번째 부분집합에는 $n_{k}$개의 원소를 포함하는 $k$개의 부분집합으로 분할될 수 있는 경우의 수는 $$\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}$$ 이다.

증명: 첫번째 부분집합의 원소가 되는 $n_{1}$개의 원소들은 $\displaystyle\binom{n}{n_{1}}$가지로 선택되고, 두번째 부분집합의 원소가 되는 $n_{2}$개의 원소들은 $\displaystyle\binom{n-n_{1}}{n_{2}}$가지로 선택되고, 세번째 부분집합의 원소가 되는 $n_{3}$개의 원소들은 $\displaystyle\binom{n-n_{1}-n_{2}}{n_{3}}$가지로 선택된다. 이 과정을 계속하면 $$\begin{align*}&\binom{n}{n_{1}}\binom{n-n_{1}}{n_{2}}\binom{n-n_{1}-n_{2}}{n_{3}}\cdots\binom{n-n_{1}-n_{2}-\cdots-n_{k-1}}{n_{k}}\\&=\frac{n!}{n_{1}!(n-n_{1})!}\frac{(n-n_{1})!}{n_{2}!(n-n_{1}-n_{2})!}\cdots\frac{(n-n_{1}-n_{2}-\cdots-n_{k-1})!}{n_{k}!0!}\\&=\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}\end{align*}$$ 이다.(이 것을 분할(partition)이라고 한다)

$n$개의 다른 개체들 중에서 중복을 허용하여 $k$개를 선택하는 경우의 수는 $$_{n}H_{k}=\binom{n+k-1}{k}$$ 이다.(중복조합)

증명: $n$개 중에서 $k$개를 중복을 허용해서 선택하는 경우의 수는 $k-1$개의 칸막이를 이용해 어떤 대상을 중복할 지를 조절하면 되므로, 이 경우의 수는 $n+k-1$개 중에서 $k$개를 선택하는 경우의 수와 같고 따라서 $$_{n}H_{k}=\binom{n+k-1}{k}$$ 이다.  

 

6명을 원탁에 앉게 하는 경우의 수는

(i) 6가지의 같은 경우가 나타나므로 $\displaystyle\frac{6!}{6}=5!=120$이다.

(ii) 한 사람을 고정시킨 다음 나머지 5명을 배열하면 되므로 $(6-1)!=5!=120$이다.

문자 ABBCCC를 일렬로 나열하는 경우의 수는 B가 2개, C가 3개 있으므로 $\displaystyle\frac{6!}{2!3!}=60$이다. 

방정식 $x+y=5$의 음이 아닌 정수해의 개수는 $\displaystyle_{2}H_{5}=\binom{2+5-1}{5}=\binom{6}{5}=6$이다.

$(x+y)^{n}$의 이항전개는 $$(x+y)^{n}=\sum_{r=0}^{n}{\binom{n}{r}x^{r}y^{n-r}}$$ 이고, $x^{r}y^{n-r}$의 계수 $\displaystyle\binom{n}{r}$을 이항계수(binomial coefficient)라고 한다. 이때 이항계수는 다음의 성질을 갖는다.

(1) $\displaystyle\binom{n}{r}=\binom{n}{n-r}$

(2) $\displaystyle2^{n}=\sum_{r=0}^{n}{\binom{n}{r}}$

(3) $\displaystyle\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$(파스칼의 삼각형, Pascal's triangle)

(4) $\displaystyle\binom{m+n}{r}=\sum_{k=0}^{r}{\binom{m}{k}\binom{n}{r-k}}$

증명:

(1) 이항계수의 정의로부터 $$\binom{n}{n-r}=\frac{n!}{(n-r)!(n-(n-r))!}=\frac{n!}{(n-r)!r!}=\frac{n!}{r!(n-r)!}=\binom{n}{r}$$ 이다.

(2) 등식 $\displaystyle(x+y)^{n}=\sum_{r=0}^{n}{\binom{n}{r}x^{r}y^{n-r}}$에 $x=1,\,y=1$을 대입한다.

(3) $(x+1)^{n}=x(x+1)^{n-1}+(x+1)^{n}$이고, $(x+1)^{n}$에서 $x^{r}$의 계수는 $\displaystyle\binom{n}{r}$, $(x+1)^{n-1}$에서 $x^{r}$의 계수는 $\displaystyle\binom{n-1}{r}$, $x(x+1)^{n-1}$에서 $x^{r}$의 계수는 $\displaystyle\binom{n-1}{r-1}$이므로 다음 식이 성립한다 $$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$

(4) $$(x+1)^{m+n}=(x+1)^{m}(x+1)^{n}$$ 이고 $(x+1)^{m+n}$에서 $x^{r}$의 계수는 $\displaystyle\binom{m+n}{k}$이고, 등식 $$\begin{align*}(x+1)^{m}(x+1)^{n}=\left\{\binom{m}{0}+\binom{m}{1}x+\cdots+\binom{m}{m}x^{m}\right\}\left\{\binom{n}{0}+\binom{n}{1}x+\cdots+\binom{n}{n}x^{n}\right\}\end{align*}$$ 을 이용하여 $x^{r}$의 계수를 구하면 $$\binom{m}{0}\binom{n}{r}+\binom{m}{1}\binom{n}{r-1}+\binom{m}{2}\binom{n}{r-2}+\cdots+\binom{m}{r}\binom{n}{0}=\sum_{k=0}^{r}{\binom{m}{k}\binom{n}{r-k}}$$ 이므로 등식 $$\binom{m+n}{r}=\sum_{k=0}^{r}{\binom{m}{k}\binom{n}{r-k}}$$ 가 성립한다.

참고자료:

John E Freund's Mathematical Statistics with Applications 8th edition, Irwin Miller, Marylees Miller, Pearson

Introduction to Mathematical Statistics 7th edition, Hogg, McKean, Craig, Pearson

수리통계학, 허문열, 송문섭 공저, 박영사