jjycjn's Math Storehouse

이번 글에서는 몇 가지 조합 항등식(combination identity)들을 대수적인 방법이나 기타 다른 방법을 이용하지 않고 오직 조합론적 증명(combinatorial proof) 방법만을 이용하여 증명하려고 한다. 모든 증명은 기본적인 Double counting (한가지 대상을 두가지 다른 방법으로 셈하여 그 두개의 셈이 서로 같음을 보이는 방법)을 바탕으로 하고 있다. $\displaystyle{{n \choose r}= {n \choose n-r}}$증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하는 경우의 수 ${n \choose r}$은 $n$명의 지원자 중에서 $n-r$명의 불합격자를 선택하는 경우의 수 ${n \choose n-r}$와 같다. $\displaystyle{{n ..