Vandermonde identitet

Vandermonde-identiteten (eller Vandermonde-konvolutionen ) er følgende identitet for binomiale koefficienter :

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

for alle ikke-negative heltal r , m , n . Identiteten er opkaldt efter Alexander Theophilus Vandermonde (1772), selvom den var kendt så tidligt som i 1303 af den kinesiske matematiker Zhu Shijie . Se Askeys artikel om identitetshistorie [1] .

Der er en q -analog til denne sætning, kaldet q -Vandermonde-identiteten .

Vandermonde-identiteten kan generaliseres på mange måder, herunder identiteten

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

Beviser

Algebraisk bevis

I det generelle tilfælde har produktet af to polynomier af grader m og n formlen

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

hvor vi bruger konventionen at a i = 0 for alle heltal i > m og b j = 0 for alle heltal j > n . Ifølge Newtons binomiale ,

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

Ved at bruge Newtons binomiale formel også for potenserne af m og n , og derefter ovenstående formel for produktet af polynomier, får vi

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

hvor ovenstående konventioner for polynomiale koefficienter er i overensstemmelse med definitionen af binomiale koefficienter, da de giver nul for alle og . $i>m$ $j>n$

Ved at sammenligne koefficienterne for x r får vi Vandermonde-identiteten for alle heltal r med . For store værdier af r er begge sider af Vandermonde-identiteten nul ifølge definitionen af binomiale koefficienter. $0\leqslant r\leqslant m+n$

Kombinatorisk bevis

Vandermonde-identiteten tillader også et kombinatorisk bevis ved hjælp af dobbelttælling . Antag, at udvalget består af m mænd og n kvinder. På hvor mange måder kan der dannes et underudvalg af r medlemmer? Svaret er

{m+n \choose r}.

Dette tal er summen over alle mulige værdier k af antallet af udvalg bestående af k mænd og kvinder: $rk$

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

Geometrisk bevis

Lad os tage et rektangulært gitter af rx (m+nr) kvadrater. Eksisterer

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

stier, der starter fra nederste venstre hjørne og slutter i øverste højre hjørne, og bevæger sig kun til højre og op (som et resultat har vi r overgange til højre og m + nr overgange op (eller omvendt) i en hvilken som helst rækkefølge, og der vil være m + n overgange i alt ). Lad os betegne det nederste venstre hjørne som (0,0) .

Der er stier, der starter ved (0,0) og slutter ved (k,mk) , da der skal laves k højrespring og mk opspring (stiens længde vil være m ). På samme måde, hvis der er stier, der starter ved (k,mk) og slutter ved (r,m+nr) , som et resultat af, at rk springer til højre og (m+nr)-(mk) bevæger sig op, vil længden af sti vil være rk + (m+ nr)-(mk) = n . Således er der ${\binom {m}{k))$ ${\binom {n}{rk))$

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

Stier, der starter ved (0,0) , slutter ved (r, m+nr) og går gennem (k, mk) . Dette sæt stier er en delmængde af alle stier, der starter ved (0,0) og slutter ved (r, m+nr) , så summen er fra k=0 til k=r (fordi punktet (k, mk) skal ligge inde i rektanglet) vil give det samlede antal stier, der starter ved (0,0) og slutter ved (r, m+nr) .

Generaliseringer

Generaliseret Vandermonde-identitet

Man kan generalisere Vandermonde-identiteten som følger:

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

Denne identitet kan opnås ved hjælp af algebraisk afledning (som ovenfor) ved hjælp af mere end to polynomier, eller gennem den sædvanlige dobbelttælling .

På den anden side kan man vælge elementer fra det første sæt af elementer, derefter vælge elementer fra et andet sæt, og så videre, for alle sådanne sæt, indtil der ikke er valgt elementer fra sættene. Således udvælges elementer fra venstre side af identiteten, hvilket er nøjagtigt det samme, som det gøres i højre side. $\textstyle k_{1}$ $\textstyle n_{1}$ $\textstyle k_{2}$ $\tekststil s$ $\textstyle m$ $\tekststil s$ $\textstyle m$ ${\displaystyle \textstyle n_{1}+\dots +n_{p))$

Zhu-Vandermonde-identiteten

Identiteten generaliserer til ikke-heltalsargumenter. I dette tilfælde er identiteten kendt som Zhu-Vandermonde-identiteten (se Askays artikel [1] ) og har formen

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

for generelle komplekse tal s og t og ikke-negative heltal n . Identiteten kan bevises analogt med beviset ovenfor ved at gange binomialrækken for og og sammenligne termerne med binomialrækken for . ${\displaystyle (1+x)^{s))$ ${\displaystyle (1+x)^{t))$ ${\displaystyle (1+x)^{s+t))$

Denne identitet kan omskrives i form af faldende Pochhammer-symboler

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

I denne form genkendes identiteten tydeligt som en skyggeversion af Newton-binomialet (for andre skyggeversioner af Newton-binomialet, se Sequence of polynomials of binomial type [ ). Zhu-Vandermonde-identiteten kan også ses som et særligt tilfælde af Gauss hypergeometriske sætning , som siger, at

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

hvor er den hypergeometriske funktion , og er gammafunktionen . Hvis vi tager a = − n i Zhu-Vandermonde-identiteten , får vi ${\displaystyle \;_{2}F_{1))$ $\Gamma (n+1)=n!$

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

Rothe-Hagen-identiteten er en yderligere generalisering af denne identitet.

Hypergeometrisk sandsynlighedsfordeling

Hvis begge dele af identiteten divideres med udtrykket til venstre, så bliver summen lig med 1, og vilkårene kan tolkes som sandsynligheder. Den resulterende sandsynlighedsfordeling kaldes den hypergeometriske fordeling . Denne fordeling svarer til sandsynlighedsfordelingen af antallet af røde kugler i et udvalg ( uden erstatning ) af r kugler fra en urne indeholdende n røde og m blå kugler.

Se også

Pascals regel
Stick Identity
Rote-Hagen identitet

Noter

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

Litteratur

Richard Askey . Ortogonale polynomier og specielle funktioner. - Philadelphia, PA: SIAM, 1975. - T. 21. - P. viii + 110. — (Regional konferencerække i anvendt matematik).