Vandermondova konvolúcia

Vandermondova konvolúcia alebo Vandermondova identita je kombinatorická identita pomenovaná po francúzskom matematikovi Alexandre-Théophile Vandermonde, ktorý s ňou prišiel v roku 1772. Znenie identity je

kde  je binomický koeficient. Napriek tomu, že je konvolúcia pomenovaná po Vandermondovi, v skutočnosti pochádza už z roku 1303, kedy ju objavil čínsky matematik Ši-ťie Ču.

 Algebrický dôkaz 

Vo všeobecnosti platí nasledujúci vzťah pre súčin dvoch polynómov stupňov m a r:

pričom používame konvencu, že ai = 0 pre i > m a bj = 0 pre všetky j > n. Z binomickej vety,

Ak použijeme binomickú vetu aj pre exponenty m a n a potom použijeme hore uvedený vzťah na násobenie polynómov, dostaneme

Vidno, že hore uvedená konvencia ohľadom koeficientov polynómov súhlasí s definíciou binomického koeficientu, keďže pre i > m, v resp. j > n sú oba binomické koeficienty nulové.

Dôkaz Vandermondovej konvolúcie pre 0 ≤ r ≤ m + n teraz možno dostať jednoduchým porovnaním koeficientov pri rovnakých mocninách xr v prvej a poslednej sume. Z definície binomických koeficientov vyplýva, že pre ostatné hodnoty r sú obe strany rovnosti nulové, a preto identita platí pre všetky hodnoty r.

 Kombinatorický dôkaz 

Vandermondova konvolúcia sa okrem "klasického" algebraického dôkazu dá dokázať aj pomocou jej kombinatorického významu. Takýto dôkaz je, samozrejme, podstatne jednoduchší, aj keď o niečo menej exaktný ako prvý uvedený. To však nemení nič na jeho korektnosti.

Predstavme si nasledujúcu situáciu: v triede je m chlapcov a n dievčat. Koľkými spôsobmi môže učiteľ vyvolať k tabuli r žiakov (na poradí vyvolávania nezáleží)? Prvá možnosť je vybrať spomedzi všetkých m+n žiakov triedy r žiakov, čo vedie k riešeniu

.

Na druhej strane môžeme postupovať tak, že sčítame počet všetkých možností, pre ktorých bolo vyvolaných r chlapcov a 0 dievčat, r-1 chlapcov a 1 dievča, atď. až 0 chlapcov a r dievčat. A tento postup vedie k výsledku

Keďže sú však oba výsledky správne, nutne sa musia rovnať. Tým je Vandermondova konvolúcia dokázaná.

 Pozri aj 
 Pascalov trojuholník

 Zdroj 

Kategória:Kombinatorika