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

Identitet glasi:

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

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 $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 $k$-članih podskupova od $S_{3}$ za neki fiksni $k\in \mathbb {N} .$ Njih ima ${\binom {|S_{3}|}{k}}={\binom {m+n}{k}}.$

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

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

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