Identiteit van Vandermonde

De identiteit van Vandermonde, ook convolutie van Vandermonde geheten, is een identiteit uit de combinatoriek, die een betrekking tussen binomiaalcoëfficiënten geeft:

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

De identiteit is vernoemd naar de Franse wiskundige Alexandre-Théophile Vandermonde, maar werd al in 1303 vermeld door de Chinese wiskundige Zhu Shijie (Chu Shi-Chieh).

Bewijs

De identiteit van Vandermonde kan bewezen worden op meerdere manieren.

Combinatorisch bewijs

Het aantal mogelijkheden om $r$ elementen te kiezen uit een verzameling van $n$ elementen van de ene soort en $m$ elementen van een andere soort, is

$n+m \choose r$.

Deze mogelijkheden kunnen ook gerealiseerd worden door eerst $k$ elementen te kiezen uit de eerste soort, wat kan op

$n \choose k$

verschillende manieren, en vervolgens $r-k$ uit de andere soort, wat kan op

$m \choose {r-k}$

verschillende manieren. Dat betekent

${n \choose k}{m \choose {r-k}}$

mogelijkheden met $k$ elementen van de eerste soort. Sommeren over $k$ levert alle mogelijkheden, wat de identiteit van Vandermonde oplevert.

Algebraïsch bewijs

Er is een sterke relatie tussen combinatoriek en het binomium van Newton. Daarom is er ook een overeenkomstig algebraïsch bewijs. Enerzijds geldt:

$(1+x)^{n+m}=\sum _{r=0}^{n+m}{n+m \choose r}x^{r}$

en anderzijds:

$(1+x)^{n+m}=(1+x)^{n}(1+x)^{m}=\left(\sum _{i=0}^{n}{n \choose i}x^{i}\right)\left(\sum _{j=0}^{m}{m \choose j}x^{j}\right)=\sum _{r=0}^{n+m}\sum _{i+j=r}{n \choose i}{m \choose j}x^{i+j}$.

Gelijkstellen van de coëfficiënten van $x^{r}$ levert de identiteit van Vandermonde.