Vandermonden identiteetti

Vandermonde-identiteetti (tai Vandermonde-konvoluutio ) on seuraava binomikertoimien identiteetti :

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

kaikille ei-negatiivisille kokonaisluvuille r , m , n . Identiteetti on nimetty Alexander Theophilus Vandermonden (1772) mukaan, vaikka kiinalainen matemaatikko Zhu Shijie tunsi sen jo vuonna 1303 . Katso Askeyn artikkeli identiteetin historiasta [1] .

Tälle lauseelle on olemassa q -analogi, jota kutsutaan q -Vandermonde-identiteetiksi .

Vandermonde-identiteettiä voidaan yleistää monella tapaa, mukaan lukien identiteetti

{n_{1}+\pisteet +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}}

Todisteet

Algebrallinen todiste

Yleisessä tapauksessa kahden polynomin, joiden asteet m ja n , tulolla on kaava

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

jossa käytämme sopimusta, että a i = 0 kaikille kokonaisluvuille i > m ja b j = 0 kaikille kokonaisluvuille j > n . Newtonin binomiaalin mukaan

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

Käyttämällä Newtonin binomikaavaa myös potensseille m ja n , ja sitten yllä olevaa kaavaa polynomien tulolle, saadaan

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

missä edellä mainitut polynomikertoimien sopimukset ovat yhdenmukaisia binomikertoimien määritelmän kanssa, koska ne antavat nollan kaikille ja . $i>m$ $j>n$

Vertaamalla x r : n kertoimia saadaan Vandermonde-identiteetti kaikille kokonaisluvuille r , joissa on . Suurille r :n arvoille Vandermonden identiteetin molemmat puolet ovat nolla binomiaalikertoimien määritelmän mukaan. $0\leqslant r\leqslant m+n$

Kombinatorinen todistus

Vandermonde-identiteetti mahdollistaa myös kombinatorisen todistuksen käyttämällä kaksoislaskentaa . Oletetaan, että komiteassa on m miestä ja n naista. Kuinka monella tavalla voidaan muodostaa r - jäseninen alakomitea? Vastaus on

{m+n \choose r}.

Tämä luku on k miehen ja naisen komiteoiden lukumäärän kaikkien mahdollisten arvojen k summa: $rk$

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

Geometrinen todiste

Otetaan rx (m+nr) neliöiden suorakaiteen muotoinen hila. Olemassa

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

polut alkavat vasemmasta alakulmasta ja päättyvät oikeaan yläkulmaan, liikkuvat vain oikealle ja ylös (seurauksena meillä on r siirtymiä oikealle ja m + nr siirtymiä ylös (tai päinvastoin) missä tahansa järjestyksessä, ja siirtymiä on yhteensä m + n ). Merkitään vasempaan alakulmaan (0,0) .

On polkuja, jotka alkavat (0,0) ja päättyvät (k,mk) , koska on tehtävä k hyppyä oikealle ja mk ylös (polun pituus on m ). Vastaavasti, jos on polkuja, jotka alkavat (k,mk) ja päättyvät (r,m+nr) , seurauksena rk hyppää oikealle ja (m+nr)-(mk) siirtyy ylöspäin, polku on rk + (m+ nr)-(mk) = n . Näin ollen on ${\binom {m}{k}}$ ${\binom {n}{rk))$

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

Polut alkaen (0,0) , päättyen (r, m+nr) ja kulkee (k, mk) . Tämä polkujoukko on osajoukko kaikista polkuista, jotka alkavat (0,0) ja päättyvät kohtaan (r, m+nr) , joten summa on välillä k=0 arvoon k=r (koska pisteen (k, mk) täytyy sijaitsee suorakulmion sisällä) antaa polkujen kokonaismäärän alkaen (0,0) ja päättyen (r, m+nr) .

Yleistykset

Yleistetty Vandermonde-identiteetti

Vandermonden identiteettiä voidaan yleistää seuraavasti:

\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}+\pisteet +n_{p} \choose m}

Tämä identiteetti voidaan saada käyttämällä algebrallista johtamista (kuten edellä) käyttämällä useampaa kuin kahta polynomia tai käyttämällä tavanomaista kaksoislaskentaa .

Toisaalta voidaan valita elementtejä ensimmäisestä elementtijoukosta, sitten valita elementtejä toisesta joukosta ja niin edelleen, kaikille sellaisille joukoille, kunnes yhtään elementtiä ei valita joukoista. Eli elementit valitaan identiteetin vasemmalta puolelta, mikä on täsmälleen sama kuin oikealla puolella. $\textstyle k_{1}$ $\textstyle n_{1}$ $\textstyle k_{2}$ $\textstyle s$ $\textstyle m$ $\textstyle s$ $\textstyle m$ ${\displaystyle \textstyle n_{1}+\pisteet +n_{p))$

Zhu-Vandermonden identiteetti

Identiteetti yleistyy ei-kokonaislukuargumenteiksi. Tässä tapauksessa identiteetti tunnetaan nimellä Zhu-Vandermonde-identiteetti (katso Askayn artikkeli [1] ) ja sen muoto

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

yleisille kompleksiluvuille s ja t sekä ei-negatiivisille kokonaisluvuille n . Identtisyys voidaan todistaa analogisesti yllä olevan todisteen kanssa kertomalla binomisarja ja vertaamalla termejä binomisarjaan . ${\näyttötyyli (1+x)^{s}}$ ${\näyttötyyli (1+x)^{t))$ ${\näyttötyyli (1+x)^{s+t))$

Tämä identiteetti voidaan kirjoittaa uudelleen vähenevien Pochhammer-symbolien suhteen

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

Tässä muodossa identiteetti tunnistetaan selvästi Newton-binomiaalin varjoversioksi ( muita Newton-binomin varjoversioita varten, katso Binomityyppisten polynomien sekvenssi ). Zhu-Vandermonden identiteettiä voidaan pitää myös Gaussin hypergeometrisen lauseen erikoistapauksena , joka sanoo, että

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

missä on hypergeometrinen funktio ja gammafunktio . Jos otamme Zhu - Vandermonden identiteetissä = − n , saamme ${\displaystyle \;_{2}F_{1))$ $\Gamma (n+1)=n!$

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

Rothe-Hagen-identiteetti on tämän identiteetin lisäyleistys.

Hypergeometrinen todennäköisyysjakauma

Jos molemmat identiteetin osat jaetaan vasemmalla olevalla lausekkeella, niin summa on yhtä suuri kuin 1 ja termit voidaan tulkita todennäköisyyksiksi. Tuloksena olevaa todennäköisyysjakaumaa kutsutaan hypergeometriseksi jakaumaksi . Tämä jakauma vastaa punaisten pallojen lukumäärän todennäköisyysjakaumaa valitussa ( korvaamatta ) r palloa uurnasta, joka sisältää n punaista ja m sinistä palloa.

Katso myös

Pascalin sääntö
Stick Identity
Rote-Hagen-identiteetti

Muistiinpanot

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

Kirjallisuus

Richard Askey . Ortogonaaliset polynomit ja erikoisfunktiot. - Philadelphia, PA: SIAM, 1975. - T. 21. - P. viii + 110. — (Soveltavan matematiikan alueellinen konferenssisarja).