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

{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k},\qquad m,n,r\in\mathbb{N}_0,

kde {n \choose k} 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.

Algebraický dôkaz[upraviť | upraviť zdroj]

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

\biggl(\sum_{i=0}^m a_ix^i\biggr) \biggl(\sum_{j=0}^n b_jx^j\biggr)
= \sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r a_k b_{r-k}\biggr) x^r,

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

(1+x)^{m+n} = \sum_{r=0}^{m+n} {m+n \choose r}x^r.

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

\begin{align}
\sum_{r=0}^{m+n} {m+n \choose r}x^r
&= (1+x)^{m+n}\\
&= (1+x)^m (1+x)^n \\
&= \biggl(\sum_{i=0}^m {m\choose i}x^i\biggr)
   \biggl(\sum_{j=0}^n {n\choose j}x^j\biggr)\\
&=\sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r {m\choose k} {n\choose r-k}\biggr) x^r.
\end{align}

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

{m + n \choose r}.

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

\sum_{k=0}^r{m \choose k}{n \choose r-k}.

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.