Vandermonde identitás

A Vandermonde-azonosság (vagy Vandermonde-konvolúció ) a következő binomiális együtthatók azonossága :

{\displaystyle {m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose rk))

bármely r , m , n nemnegatív egész számra . Az identitás Alexander Theophilus Vandermonde (1772) nevéhez fűződik, bár Zhu Shijie kínai matematikus már 1303-ban ismerte . Lásd Askey cikkét az identitás történetéről [1] .

Ennek a tételnek van egy q -analógja , a q -Vandermonde azonosság .

A Vandermonde-identitás sokféleképpen általánosítható, beleértve az identitást is

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

Bizonyíték

Algebrai bizonyítás

Általános esetben két m és n fokú polinom szorzatának van a képlete

{\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},

ahol azt a konvenciót alkalmazzuk, hogy a i = 0 minden i > m egészre és b j = 0 minden j > n egészre . Newton binomiálisa szerint

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

Newton binomiális képletét felhasználva m és n hatványaira is , majd a fenti képletet a polinomok szorzatára, megkapjuk

{\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 rk}{\biggr )}x^{r},\ vége{igazított}}

ahol a polinomiális együtthatókra vonatkozó fenti konvenciók összhangban vannak a binomiális együtthatók definíciójával, mivel nullát adnak minden és . $i>m$ $j>n$

Összehasonlítva x r együtthatóit , megkapjuk a Vandermonde-azonosságot minden r egész számra -val . Nagy r értékek esetén a Vandermonde-azonosság mindkét oldala nulla, a binomiális együtthatók meghatározása szerint. $0\leqslant r\leqslant m+n$

Kombinatorikus bizonyítás

A Vandermonde azonosság lehetővé teszi a kombinatorikus bizonyítást is kettős számlálással . Tegyük fel, hogy a bizottság m férfiból és n nőből áll. Hányféleképpen hozható létre r tagú albizottság? A válasz

{m+n \choose r}.

Ez a szám a k férfiból és nőből álló bizottságok számának összes lehetséges k értékének összege: $rk$

\sum _{k=0}^{r}{m \choose k}{n \choose rk}.

Geometriai bizonyítás

Vegyünk egy rx (m+nr) négyzetekből álló téglalap alakú rácsot. Létezik

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

a bal alsó sarokból induló és a jobb felső sarokban végződő utak, amelyek csak jobbra és felfelé haladnak (ennek eredményeként van r átmenet jobbra és m + nr átmenet felfelé (vagy fordítva) tetszőleges sorrendben, és összesen m + n átmenet lesz ). A bal alsó sarkot jelöljük (0,0) .

Vannak (0,0) -tól kezdődő és (k,mk) végződésű utak , mivel k jobbra és mk felfelé ugrást kell végrehajtani (az út hossza m lesz ). Hasonlóképpen, ha vannak olyan utak, amelyek (k,mk) -nál kezdődnek és (r,m+nr) -re végződnek, az rk jobbra ugrik és (m+nr)-(mk) eredményeként feljebb lép, a útvonal lesz rk + (m+ nr)-(mk) = n . Így van ${\binom {m}{k))$ ${\binom {n}{rk))$

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

A (0,0) -tól kezdődő , (r, m+nr) -re végződő és (k, mk)-n áthaladó utak . Ez az utak halmaza az összes (0,0) -tól kezdődő és (r, m+nr) -re végződő utak részhalmaza , tehát az összeg k=0 -tól k=r -ig terjed (mivel a (k, mk) pontnak kell ha a téglalapon belül van) megadja a (0,0) -tól kezdődő és (r, m+nr) -re végződő utak teljes számát .

Általánosítások

Általános Vandermonde-identitás

A Vandermonde identitás a következőképpen általánosítható:

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

Ez az azonosság meghatározható algebrai levezetéssel (a fentiek szerint) kettőnél több polinom használatával, vagy a szokásos kettős számlálással .

Másrészt kijelölhetünk elemeket az első elemkészletből , majd kiválaszthatunk elemeket egy másik halmazból, és így tovább, az összes ilyen halmazhoz, amíg egyetlen elemet sem választunk ki a halmazokból. Így az identitás bal oldaláról kerülnek kiválasztásra az elemek , ami pontosan ugyanaz, mint a jobb oldalon. $\textstyle k_{1}$ $\textstyle n_{1}$ $\textstyle k_{2}$ $\textstyle p$ $\textstyle m$ $\textstyle p$ $\textstyle m$ ${\displaystyle \textstyle n_{1}+\pontok +n_{p))$

A Zhu-Vandermonde identitás

Az azonosság nem egész argumentumokra általánosodik. Ebben az esetben az identitás Zhu-Vandermonde identitás néven ismert (lásd Askay cikkét [1] ), és a következő formát ölti

{\displaystyle {s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose nk))

általános s és t komplex számokra és n nemnegatív egész számokra . Az azonosság a fenti bizonyítással analógiával igazolható, ha a binomiális sorozatot megszorozzuk , és a kifejezéseket összehasonlítjuk a binomiális sorozattal . ${\megjelenítési stílus (1+x)^{s))$ ${\megjelenítési stílus (1+x)^{t))$ ${\megjelenítési stílus (1+x)^{s+t))$

Ez az identitás átírható a csökkenő Pochhammer szimbólumok formájában

{\displaystyle (s+t)_{n}=\sum _{k=0}^{n}{n \choose k}(s)_{k}(t)_{nk))

Ebben a formában az identitás egyértelműen a Newton-binomiális árnyékváltozataként ismerhető fel ( a Newton-binomiális többi árnyékváltozatához lásd : Binomiális típusú polinomok sorozata ). A Zhu-Vandermonde azonosság a Gauss hipergeometriai tétel speciális eseteként is felfogható , amely kimondja, hogy

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

ahol a hipergeometrikus függvény és a gamma függvény . Ha egy = − n -t veszünk a Zhu-Vandermonde azonosságban , akkor azt kapjuk ${\displaystyle \;_{2}F_{1))$ $\Gamma (n+1)=n!$

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

A Rothe-Hagen identitás ennek az identitásnak egy további általánosítása.

Hipergeometrikus valószínűségi eloszlás

Ha az azonosság mindkét részét elosztjuk a bal oldali kifejezéssel, akkor az összeg 1-gyel egyenlő lesz, és a tagok valószínűségként értelmezhetők. Az így kapott valószínűségi eloszlást hipergeometrikus eloszlásnak nevezzük . Ez az eloszlás megfelel a piros golyók számának valószínűségi eloszlásának egy n piros és m kék golyót tartalmazó urnából kiválasztott ( csere nélkül ) r golyóból.

Lásd még

Pascal szabálya
Stick Identity
Rote-Hagen identitás

Jegyzetek

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

Irodalom

Richard Askey . Ortogonális polinomok és speciális függvények. - Philadelphia, PA: SIAM, 1975. - T. 21. - P. viii + 110. — (Alkalmazott matematikai regionális konferenciasorozat).