Vandermondov identitet

U kombinatorici, Vandermondov identitet, koji je dobio ime po matematičaru Aleksandru-Teofilu Vandermondu, je tvrđenje da važi jednakost

${n+m \choose r}=\sum _{k=0}^{r}{n \choose k}{m \choose r-k}.$

Dokaz

Identitet se lako dokazuje korišćenjem algebarske jednakosti

${n \choose k}={n! \over k!(n-k)!},$

Ako pretpostavimo da u odeljenju ima n dečaka i m devojčica, na koliko načina je moguće izabrati r učenika? Odgovor je, naravno, izraz sa leve strane jednakosti

${n+m \choose r}.$

Sa desne strane nalazi se zbir svih mogućih izbora od r učenika takvih da je među njima k dečaka i r − k devojčica, pri čemu je k broj između 0 i r.