WikiSysop: Bot: Automatski unos stranica

2021-12-11T09:28:42Z

Bot: Automatski unos stranica

Nova stranica

'''Vandermondeov identitet''' ili '''Vandermondeova konvolucija''' je [[teorem]] u [[Kombinatorika|kombinatorici]] koji se može shvatiti kao jedan od brojnih načina prebrojavanja kombinacija svih <math>k</math>-članih [[podskup]]ova [[skup]]a koji ima <math>m + n </math> članova za zadane <math>k, m, n \in \mathbb{N} </math> uz očiti uvjet <math> k \leq m + n. </math>

Identitet glasi:
:<math>{m+n \choose k}=\sum_{i=0}^k{m \choose k}{n \choose i-k}</math>

U svojim radovima ga je [[1772.]] objavio [[Francuska|francuski]] [[Matematika|matemaričar]] i [[Kemija|kemičar]] Alexandre-Théophile Vandermonde ([[1735.]] – [[1796.]]), iako je za njega znao već [[Kina|kineski]] [[Matematika|matematičar]] Zhu Shijie u [[14. stoljeće|14. stoljeću]].

== Dokaz ==
Teorem se može dokazati [[Algebra|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>S_1 = \{1, 2, ..., m\}, S_2 = \{-1, -2, ..., -n\} </math> za <math> m, n \in \mathbb{N}. </math>

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

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

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

Slijedi da je broj kombinacija ova [[suma]]: <math>\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>{m+n \choose k}=\sum_{i=0}^k{m \choose k}{n \choose i-k}</math> za zadane <math>k, m, n \in \mathbb{N}. </math><ref>https://brilliant.org/wiki/vandermondes-identity/</ref>

== Izvori ==
{{izvori}}

[[Kategorija:Matematika]]

Vandermondeov identitet - Povijest promjena

WikiSysop: Bot: Automatski unos stranica