Identitatea Vandermonde

Identitatea Vandermonde (sau convoluția Vandermonde ) este următoarea identitate pentru coeficienții binomiali :

{m+n \alegeți r}=\sum _{k=0}^{r}{m \alegeți k}{n \alegeți rk)

pentru orice numere întregi nenegative r , m , n . Identitatea este numită după Alexander Theophilus Vandermonde (1772), deși era cunoscută încă din 1303 de matematicianul chinez Zhu Shijie . Vezi articolul lui Askey despre istoria identității [1] .

Există un q -analog al acestei teoreme, numit identitate q -Vandermonde .

Identitatea Vandermonde poate fi generalizată în multe feluri, inclusiv identitatea

{n_{1}+\dots +n_{p} \choose m}=\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1 }}{n_{2} \alege k_{2}}\cdots {n_{p} \alege k_{p}}

Dovezi

Dovada algebrică

În cazul general, produsul a două polinoame de grade m și n are formula

{\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_{rk}{\biggr )}x^{r},

unde folosim convenția că a i = 0 pentru toate numerele întregi i > m și b j = 0 pentru toate numerele întregi j > n . Conform binomului lui Newton ,

(1+x)^{m+n}=\sum _{r=0}^{m+n}{m+n \alegeți r}x^{r}.

Folosind formula binomială a lui Newton și pentru puterile lui m și n și apoi formula de mai sus pentru produsul polinoamelor, obținem

{\begin{aligned}\sum _{r=0}^{m+n}{m+n \alegeți r}x^{r}&=(1+x)^{m+n}\ \&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \alege 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 \alege k}{n \alege rk}{\biggr )}x^{r},\ sfârşit{aliniat}}

unde convențiile de mai sus pentru coeficienții polinomi sunt în concordanță cu definiția coeficienților binomi deoarece dau zero pentru toți și . $i>m$ $j>n$

Comparând coeficienții lui x r , obținem identitatea Vandermonde pentru toate numerele întregi r cu . Pentru valorile mari ale lui r , ambele părți ale identității Vandermonde sunt zero, conform definiției coeficienților binomi. $0\leqslant r\leqslant m+n$

Dovada combinatorie

Identitatea Vandermonde permite, de asemenea, o demonstrație combinatorie folosind numărarea dublă . Să presupunem că comitetul este format din m bărbați și n femei. În câte moduri se poate forma un subcomitet format din r membri? Raspunsul este

{m+n \alegeți r}.

Acest număr este suma tuturor valorilor posibile k ale numărului de comitete formate din k bărbați și femei: $rk$

\sum _{k=0}^{r}{m \alegeți k}{n \alegeți rk}.

Dovada geometrică

Să luăm o rețea dreptunghiulară de rx (m+nr) pătrate. Există

{\binom {r+(m+nr)}{r}}={\binom {m+n}{r}}

căi care pornesc din colțul din stânga jos și se termină în colțul din dreapta sus, deplasându-se doar spre dreapta și sus (ca urmare, avem r tranziții la dreapta și m + nr tranziții în sus (sau invers) în orice ordine, și vor exista m + n tranziții în total ). Să notăm colțul din stânga jos ca (0,0) .

Există căi care încep la (0,0) și se termină la (k,mk) , deoarece trebuie făcute k sarituri la dreapta și mk sărituri în sus (lungimea traseului va fi m ). În mod similar, dacă există căi care încep la (k,mk) și se termină la (r,m+nr) , ca urmare a rk sare la dreapta și (m+nr)-(mk) se deplasează în sus, lungimea calea va fi rk + (m+ nr)-(mk) = n . Astfel, există ${\binom {m}{k)}$ ${\binom {n}{rk)}$

{\binom {m}{k}}{\binom {n}{rk}}

Căi care încep la (0,0) , se termină la (r, m+nr) și trec prin (k, mk) . Acest set de căi este un subset al tuturor căilor care încep la (0,0) și se termină la (r, m+nr) , deci suma este de la k=0 la k=r (deoarece punctul (k, mk) trebuie se află în interiorul dreptunghiului) va da numărul total de căi care încep de la (0,0) și se termină la (r, m+nr) .

Generalizări

Identitate Vandermonde generalizată

Se poate generaliza identitatea Vandermonde după cum urmează:

\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \alegeți k_{1}}{n_{2} \alegeți k_{2}}\cdots {n_ {p} \choose k_{p}}={n_{1}+\dots +n_{p} \choose m}

Această identitate poate fi obținută folosind derivarea algebrică (ca mai sus) folosind mai mult de două polinoame, sau prin numărarea dublă obișnuită .

Pe de altă parte, se pot selecta elemente din primul set de elemente, apoi selecta elemente dintr-un alt set și așa mai departe, pentru toate astfel de seturi, până când nu se selectează niciun element din seturi. Astfel, elementele sunt selectate din partea stângă a identității, ceea ce este exact la fel cu ceea ce se face în partea dreaptă. $\textstyle k_{1}$ $\textstyle n_{1}$ $\textstyle k_{2}$ $\textstyle p$ $\textstyle m$ $\textstyle p$ $\textstyle m$ $\textstyle n_{1}+\dots +n_{p)$

Identitatea Zhu-Vandermonde

Identitatea se generalizează la argumente care nu sunt întregi. În acest caz, identitatea este cunoscută ca identitatea Zhu-Vandermonde (vezi articolul lui Askay [1] ) și ia forma

{s+t \alegeți n}=\sum _{k=0}^{n}{s \alegeți k}{t \alegeți nk)

pentru numere complexe generale s și t și numere întregi nenegative n . Identitatea poate fi demonstrată prin analogie cu demonstrația de mai sus prin înmulțirea seriei binomiale pentru și și comparând termenii cu seria binomială pentru . $(1+x)^{s}$ $(1+x)^{t)$ ${\displaystyle (1+x)^{s+t))$

Această identitate poate fi rescrisă în termeni de simboluri Pochhammer în scădere

(s+t)_{n}=\sum _{k=0}^{n}{n \alegeți k}(s)_{k}(t)_{nk)

În această formă, identitatea este recunoscută în mod clar ca o versiune umbră a binomului Newton (pentru alte versiuni umbră ale binomului Newton, vezi Secvență de polinoame de tip binom ). Identitatea Zhu-Vandermonde poate fi privită și ca un caz special al teoremei hipergeometrice Gauss , care afirmă că

\;_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (cab)}{\Gamma (ca)\Gamma (cb)} }

unde este funcția hipergeometrică și este funcția gamma . Dacă luăm a = − n în identitatea Zhu-Vandermonde , obținem $\;_{2}F_{1}$ $\Gamma (n+1)=n!$

{n \alege k}=(-1)^{k}{kn-1 \alege k)

Identitatea Rothe-Hagen este o generalizare suplimentară a acestei identități.

Distribuția de probabilitate hipergeometrică

Dacă ambele părți ale identității sunt împărțite la expresia din stânga, atunci suma devine egală cu 1 și termenii pot fi interpretați ca probabilități. Distribuția de probabilitate rezultată se numește distribuție hipergeometrică . Această distribuție corespunde distribuției de probabilitate a numărului de bile roșii dintr-o selecție ( fără înlocuire ) de r bile dintr-o urna care conține n bile roșii și m albastre.

Vezi și

Regula lui Pascal
Stick Identity
identitate Rote-Hagen

Note

↑ 1 2 Askey, 1975 , p. 59-60.

Literatură

Richard Askey . Polinoame ortogonale și funcții speciale. - Philadelphia, PA: SIAM, 1975. - T. 21. - P. viii + 110. — (Seria de conferințe regionale de matematică aplicată).