Vandermondeov identitet

Vandermondeov identitet ili Vandermondeova konvolucija je teorem u kombinatorici koji se može shvatiti kao jedan od brojnih načina prebrojavanja kombinacija svih $r$-članih podskupova skupa koji ima $m+n$ članova za zadane $r,m,n\in \mathbb {N}$ uz očiti uvjet $r\leq m+n.$

Identitet glasi:

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

U svojim radovima ga je 1772. objavio francuski matematičar i kemičar Alexandre-Théophile Vandermonde (1735. – 1796.), iako je za njega znao već kineski matematičar Zhu Shijie u 14. stoljeću.

Dokaz

U ovom načinu prebrojavanja naglasak je na dvama različitim svojstvima prema kojima smo jednoznačno podijelili elemente nekog skupa A. (Uzmimo primjerice da skup A čini 5 različitih mesojeda i 7 različitih biljojeda: dakle, skup A čini 12 međusobno različitih životinja, ali su oni podijeljeni po svojstvu prehrane.) Sada možemo formalno dokazati teorem.

Pretpostavimo da imamo dva skupa $S_{1}=\{1,2,...,m\},S_{2}=\{-1,-2,...,-n\}$ za $m,n\in \mathbb {N} .$

Promotrimo skup $S_{3}=S_{1}\cup S_{2}=\{-n,...,-1,1,2,...,m\}.$ Očito je onda $|S_{3}|=m+n.$

Pitamo se koliko ima različitih $r$-članih podskupova od $S_{3}$ za neki fiksni $r\in \mathbb {N} .$ Njih ima ${\binom {|S_{3}|}{r}}={\binom {m+n}{r}}.$

No, mogli smo prebrojavati na drugačiji način. Naime, od $r$ elemenata možemo odabrati $k$ elemenata iz $S_{1}$ pa nam ostane $r-k$ elemenata koje onda biramo iz $S_{2}.$ Takvih podskupova zato ima ${\binom {m}{k}}{\binom {n}{r-k}}.$

Slijedi da je broj kombinacija ova suma: ${\binom {m}{0}}{\binom {n}{r}}+{\binom {m}{1}}{\binom {n}{r-1}}+...+{\binom {m}{r}}{\binom {n}{0}}.$

Dakle, prebrojavanjem na dva načina zaista dobivamo jednakost ${m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}$ za zadane $k,m,n\in \mathbb {N} .$