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 [math]\displaystyle{ k }[/math]-članih podskupova skupa koji ima [math]\displaystyle{ m + n }[/math] članova za zadane [math]\displaystyle{ k, m, n \in \mathbb{N} }[/math] uz očiti uvjet [math]\displaystyle{ k \leq m + n. }[/math]

Identitet glasi:

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

U svojim radovima ga je 1772. objavio francuski matemarič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

Teorem se može dokazati algebarskim putem, no ovdje ćemo ga dokazati elementarnom kombinatorikom.

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 [math]\displaystyle{ S_1 = \{1, 2, ..., m\}, S_2 = \{-1, -2, ..., -n\} }[/math] za [math]\displaystyle{ m, n \in \mathbb{N}. }[/math]

Promotrimo skup [math]\displaystyle{ S_3 = S_1 \cup S_2 = \{-n, ..., -1, 1, 2, ..., m\}. }[/math] Očito je onda [math]\displaystyle{ |S_3| = m + n. }[/math]

Pitamo se koliko ima različitih [math]\displaystyle{ k }[/math]-članih podskupova od [math]\displaystyle{ S_3 }[/math] za neki fiksni [math]\displaystyle{ k \in \mathbb{N}. }[/math] Njih ima [math]\displaystyle{ \binom{|S_3|}{k} = \binom{m + n}{k}. }[/math]

No, mogli smo prebrojavati na drugačiji način. Naime, od [math]\displaystyle{ k }[/math] elemenata možemo odabrati [math]\displaystyle{ i }[/math] elemenata iz [math]\displaystyle{ S_1 }[/math] pa nam ostane [math]\displaystyle{ k - i }[/math] elemenata koje onda biramo iz [math]\displaystyle{ S_2. }[/math] Takvih podskupova zato ima [math]\displaystyle{ \binom{m}{i}\binom{n}{k - i}. }[/math]

Slijedi da je broj kombinacija ova suma: [math]\displaystyle{ \binom{m}{0}\binom{n}{k} + \binom{m}{1}\binom{n}{k - 1} + ... + \binom{m}{k}\binom{n}{0}. }[/math]

Dakle, prebrojavanjem na dva načina zaista dobivamo jednakost [math]\displaystyle{ {m+n \choose k}=\sum_{i=0}^k{m \choose k}{n \choose i-k} }[/math] za zadane [math]\displaystyle{ k, m, n \in \mathbb{N}. }[/math]