Vandermondova konvolúcia

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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á.

Zdroj[upraviť | upraviť zdroj]

Tento článok je čiastočný alebo úplný preklad článku Vandermonde's identity na anglickej Wikipédii.