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 ℕ$ uz očiti uvjet $r \leq m + n .$

Identitet glasi:

(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{n}{k}) (\binom{m}{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 ℕ .$

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 ℕ .$ 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 $(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})$ za zadane $k, m, n \in ℕ .$ ^[1]

Izvori

Predložak:Izvori

↑ Vandermonde's Identity

[1] Vandermonde's Identity

[1]

Vandermondeov identitet

Dokaz

Izvori

Navigacijski izbornik

Traži