이항 계수 항등식

이항 계수들의 합

자연수 $n$에 대하여, $$\displaystyle\sum_{k=0}^n{n \choose k}=2^n$$이 성립한다.

pf) 이항정리 $$(1+x)^n={n \choose n}x^n+{n \choose n-1}x^{n-1}+\cdots+{n \choose 1}x+{n \choose 0}$$에서, $x=1$을 대입하면 바로 유도된다.   $\blacksquare$

 

파스칼 항등식 

음이 아닌 정수 $r<n$에 대하여, $${n \choose r}={n-1 \choose r-1}+{n-1 \choose r}$$이 성립한다.

pf1) 조합론적 증명

$n$개의 물체에서 $r$개를 고른다 하자. 먼저 $n$개 중 $1$개를 고정하고 이를 $A$라 하자. 그럼 구하고자 하는 경우의 수는 $A$가 포함되는 경우와, 포함되지 않는 경우 $2$가지로 나눌 수 있다. 전자의 경우 나머지 $n−1$개 중 $r−1$개를 고르면 되므로, 가짓수는 ${n-1 \choose r-1}$이다. 후자의 경우 나머지 $n−1$개 중 $r$개를 고르면 되므로, 가짓수는 ${n-1 \choose r}$이다. 합의 법칙에 의해, 파스칼 항등식이 성립한다.   $\blacksquare$

pf2) 대수적 증명

$$\begin{eqnarray}{n-1 \choose r-1}+{n-1 \choose r}&&=\dfrac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}+\dfrac{\left(n-1\right)!}{r!\left(n-r-1\right)!}\\&&=\dfrac{\left(n-1\right)!}{r!\left(n-r\right)!}+\dfrac{n!}{r!\left(n-r\right)!}\\&&={n \choose r}\,\,\,\blacksquare\end{eqnarray}$$

 

Exponential 17 김지하