조합(nCr, combination) 공식 및 조합적 증명

1. \(_{n}\mathrm{C}_{r}=_{n}\mathrm{C}_{n-r}\)

증명) n개 중 뽑을 r개를 고를 가짓수=n개 중 뽑지 않을 (n-r)개를 고를 가짓수

 

2. \(_{n}\mathrm{C}_{r}=_{n-1}\mathrm{C}_{r}+_{n-1}\mathrm{C}_{r-1}=\)

증명) n개 중 r개를 고를 가짓수=

n개 중 1개 고정

i. 그 1개를 고름 -> 남은 (n-1)개 중 (r-1)개를 고름 \(=_{n-1}\mathrm{C}_{r-1}\)

ii. 그 1개를 고르지 않음 -> 남은 (n-1)개 중 r개를 고름 \(=_{n-1}\mathrm{C}_{r}\)

 

3. \(_{n}\mathrm{C}_{r}=\frac{n}{r}_{n-1}\mathrm{C}_{r-1}\)

증명) 계산

혹은

\(r\times_{n}\mathrm{C}_{r}=n\times_{n-1}\mathrm{C}_{r-1}\)으로 변형

n개 중 r개를 뽑고, r개 중 1개를 뽑는 상황 생각 = 좌변

이는 n개 중 1개를 먼저 뽑고 남은 (n-1)개 중 (r-1)개를 뽑는 상황 = 우변 과 같다

3번 공식 증명

 

4. \(_{n}\mathrm{C}_{0}+_{n}\mathrm{C}_{1}+\ldots+_{n}\mathrm{C}_{n}=2^n\)

우변 = n개를 각각 뽑거나 안 뽑거나 하는 가짓수

좌변 = n개를 각각 뽑거나 안 뽑거나 하면, 0개가 뽑히거나 1개가 뽑히거나 ... n개가 뽑힌다

 

5. \((_{n}\mathrm{C}_{0})^2+(_{n}\mathrm{C}_{1})^2+\ldots+(_{n}\mathrm{C}_{n})^2=_{2n}\mathrm{C}_{n}\)

빨간 공 n개, 파란 공 n개가 있다고 하자.

우변 = 총 2n개의 공 중 n개를 뽑는 가짓수

좌변 = \( _{n}\mathrm{C}_{0}\cdot _{n}\mathrm{C}_{n}\ +_{n}\mathrm{C}_{1}\cdot _{n}\mathrm{C}_{n-1} +\ldots +_{n}\mathrm{C}_{n}\cdot _{n}\mathrm{C}_{0} \)

= (빨간 공 중 0개, 파란 공 중 n개를 뽑음) + (빨간 공 중 1개, 파란 공 중 (n-1)개를 뽑음) + ... + (빨간 공 중 n개, 파란 공 중 0개를 뽑음)

 

6. \(_{r}\mathrm{C}_{r} + _{r+1}\mathrm{C}_{r} + _{r+2}\mathrm{C}_{r}+ \ldots + _{n}\mathrm{C}_{r} = _{n+1}\mathrm{C}_{r+1}\)

(n+1)개의 공에 번호 1, 2, ..., (n+1)을 붙이자. 그 중 (r+1)개를 뽑는다면, 뽑힌 공 중 가장 큰 번호를 가진 공이 있다. 

가장 큰 번호는 (r+1) 이상이다.

가장 큰 번호가 (r+1)일 때 : 번호가 r 이하인 공을 r개 뽑아야 하므로 \(_{r}\mathrm{C}_{r}\)

가장 큰 번호가 (r+2)일 때 : \( _{r+1} \mathrm{C}_r \)

...

가장 큰 번호가 (n+1)일 때 : \(_{n}\mathrm{C}_{r}\)

 

이항정리 등을 쓰지 않고 간단히 증명할 수 있는 공식이 더 떠오르면 추가하겠다.