방데르몽드 항등식

진술

음이 아닌 정수 [math]\displaystyle{ n,m,r }[/math]에 대해

[math]\displaystyle{ \sum_{k=0}^r \binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r} }[/math]

이 성립한다.

증명

대수적 증명

추가바람

조합적 증명

집합 [math]\displaystyle{ S,T }[/math]를 [math]\displaystyle{ S=\{1,2,\cdots, n\} }[/math], [math]\displaystyle{ T=\{n+1,n+2,\cdots, n+m\} }[/math]로 정의하자. 그러면 [math]\displaystyle{ S\cup T }[/math]에서 서로 다른 [math]\displaystyle{ r }[/math]개를 뽑는 경우의 수는 [math]\displaystyle{ \binom{n+m}{r} }[/math]이다. 한편 [math]\displaystyle{ S }[/math]에서 서로 다른 [math]\displaystyle{ k }[/math]개를 뽑고 [math]\displaystyle{ T }[/math]에서 서로 다른 [math]\displaystyle{ r-k }[/math]개를 뽑는 경우의 수는 [math]\displaystyle{ \binom{n}{k}\binom{m}{r-k} }[/math]이다. [math]\displaystyle{ k=0,1,\cdots, r }[/math]일 때를 모두 더하면 [math]\displaystyle{ S\cup T }[/math]에서 서로 다른 [math]\displaystyle{ r }[/math]개를 뽑는 경우의 수와 같으므로 원하는 결론을 얻는다.