[확률과통계 기초] 1-8. 조합의 성질 (2) $_{n}C_{r}=_{n-1}C_{r}+_{n-1}C_{r-1}$ 직관적이해와 증명

지난시간에 이어서 조합의 성질을 알아봅시다. 오늘은 아래 두 성질 중 두번째 성질을 공부해보겠습니다. 

1) $_{n}C_{r}=_{n}C_{n-r}$
2) $_{n}C_{r}=_{n-1}C_{r}+_{n-1}C_{r-1}$

 

$n$개에서 $r$개를 뽑는 것과, $n-1$개에서 $r$개를 뽑고 $n-1$개에서 $r-1$개를 뽑는 것의 경우의 수가 같다는 성질입니다. 숫자를 넣어 보면 아래와 같습니다. 

$_{5}C_{3}=_{4}C_{3}+_{4}C_{2}$

수학적으로 증명하기 전에 직관적으로 이해해봅시다. ABCDE 중에 3개를 뽑는 경우를 생각해 봅시다. 

ABC
ABD
ABE
...

위 경우는 둘로 나눌 수 있습니다. A가 들어있는 경우와 A가 들어있지 않은 경우입니다. 

 

A가 들어간 경우의 수는 A를 제외한 나머지 4개 중 2개를 뽑는 경우의 수와 같습니다. A를 제외한 4개에서 2개를 뽑고, 마지막에 A를 끼워넣으면 ABCDE에서 3개를 뽑으면서 A가 반드시 들어있는 경우가 됩니다. 조합으로 계산하면 $_{4}C_{2}$ 입니다. 

 

A가 들어가지 않은 경우는 A를 제외한 나머지 4개에서 3개를 뽑는 경우의 수와 같습니다. $_{4}C_{3}$ 입니다. 전체 경우의 수는 두 경우의 합과 같습니다. 따라서 아래 등식이 성립합니다. 

$_{5}C_{3}=_{4}C_{3}+_{4}C_{2}$

이번에는 수학적으로 증명해봅시다. 

$_{n}C_{r}=_{n-1}C_{r}+_{n-1}C_{r-1}$

우변은 아래와 같이 계산됩니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=\frac{(n-1)!}{(n-1-r)!r! }+\frac{(n-1)!}{  (n-r)! (r-1)!}$

우변의 첫항의 분자와 분모에 (n-r)을 곱해줍니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=\frac{(n-1)!(n-r)}{ (n-r)! r!}+\frac{(n-1)!}{  (n-r)! (r-1)!}$

우변의 두번째 항을 아래와 같이 변형합시다. 분자와 분모에 r을 곱했습니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=\frac{(n-1)!(n-r)}{ (n-r)! r!}+\frac{(n-1)! \ r}{ (n-r)! r!}$

통분하고 분자를 계산합니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=\frac{(n-1)!\ n}{  (n-r)! r!}$

분자는 n! 입니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=\frac{n!}{ (n-r)! r!}$

우변은 nCr 과 같습니다. 

$_{n-1}C_{r}+_{n-1}C_{r-1}=_{n}C_{r}$

조합의 두번째 성질이 증명되었습니다. 

 

 

#영상 강의