Identiteit van Vandermonde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

De identiteit van Vandermonde kan bewezen worden op meerdere manieren.

Combinatorisch bewijs[bewerken]

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 rk 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[bewerken]

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 xr levert de identiteit van Vandermonde.