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

${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.

Algebrický dôkaz

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_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{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 a_i = 0 pre i > m a b_j = 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{aligned}\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{aligned}}$

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 x^r 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

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

Pozri aj

• Pascalov trojuholník

Zdroj

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