Vandermondes identitet

I kombinatorik är Vandermondes identitet (eller Vandermondes faltning ) följande identitet för binomialkoefficienter :

{m+n \choose r}=\summa _{k=0}^{r}{m \choose k }{n \välj rk}

för alla icke-negativa heltal r , m , n . Identiteten är uppkallad efter Alexandre-Théophile Vandermonde (1772), även om den var känd redan 1303 av den kinesiske matematikern Zhu Shijie .

Det finns en q -analog till denna sats som kallas q -Vandermonde-identiteten .

Vandermondes identitet kan generaliseras på många sätt, inklusive till 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}}.

Bevis

Algebraiskt bevis

sett ges produkten av två polynom med grader m respektive n av

{\biggl (} \sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\summa _{j=0}^{n}b_{j}x^{ j}{\biggr )}=\summa _{r=0}^{m+n}{\biggl (}\summa _{k=0}^{r}a_{k}b_{rk}{\biggr )}x^{r},

där vi använder konventionen att a _i = 0 för alla heltal i > m och b _j = 0 för alla heltal j > n . Genom binomialsatsen ,

(1+x)^{m+n}=\summa _{r=0}^{m+n}{m+n \välj r}x^{r}.

Genom att använda binomialsatsen även för exponenterna m och n , och sedan ovanstående formel för produkten av polynom, får vi

{\begin{aligned}\sum _{ r=0}^{m+n}{m+n \välj r}x^{r}&=(1+x)^{m+n}\\&=(1+x)^{m}( 1+x)^{n}\\&={\biggl (}\summa _{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 ( }\summa _{k=0}^{r}{m \choose k}{n \choose rk}{\biggr )}x^{r},\end{aligned}}

där ovanstående konvention för polynomens koefficienter överensstämmer med definitionen av de binomiala koefficienterna, eftersom båda ger noll för alla i > m respektive j > n .

Genom att jämföra koefficienter för x ^r följer Vandermondes identitet för alla heltal r med 0 ≤ r ≤ m + n . För större heltal r är båda sidor av Vandermondes identitet noll på grund av definitionen av binomialkoefficienter.

Kombinatoriskt bevis

Vandermondes identitet medger också ett kombinatoriskt dubbelräkningsbevis , enligt följande. Anta att en kommitté består av m män och n kvinnor. På hur många sätt kan en underkommitté med r -medlemmar bildas? Svaret är

{m+n \choose r}.

Svaret är också summan över alla möjliga värden av k , av antalet underkommittéer bestående av k män och r − k kvinnor:

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

Geometriskt bevis

Ta ett rektangulärt rutnät av r x ( m + n − r ) kvadrater. Det finns

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

banor som börjar på det nedre vänstra hörnet och som bara rör sig uppåt eller åt höger, slutar i det övre högra hörnet (detta beror på att r höger drag och m + n - r upp drag måste göras (eller vice versa) i valfri ordning, och den totala väglängden är m + n ). Kalla det nedre vänstra hörnet (0, 0).

Det finns ${\binom {m}{k}}$ banor som börjar på (0, 0) som slutar på ( k , m − k ), eftersom k drag åt höger och m − k drag uppåt måste göras (och väglängden är m ). På liknande sätt finns det ${\binom {n}{rk}}$ banor som börjar på ( k , m − k ) som slutar på ( r , m + n − r ), totalt av r − k högerdrag och ( m + n − r ) − ( m − k ) rörelser uppåt måste göras och väglängden måste vara r − k + ( m + n − r ) − ( m − k ) = n . Det finns alltså

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

banor som börjar vid (0, 0), slutar vid ( r , m + n − r ), och går igenom ( k , m − k ). Detta är en delmängd av alla banor som börjar vid (0, 0) och slutar vid ( r , m + n − r ), så summan från k = 0 till k = r (som punkten ( k , m − k ) är begränsat till att vara inom kvadraten) för att erhålla det totala antalet banor som börjar vid (0, 0) och slutar vid ( r , m + n − r ).

Generaliseringar

Generaliserade Vandermondes identitet

Man kan generalisera Vandermondes identitet på följande sätt:

\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}.

Denna identitet kan erhållas genom den algebraiska härledningen ovan när fler än två polynom används, eller genom ett enkelt dubbelräkningsargument .

Å ena sidan väljer man $\textstyle k_{1}$ element ur en första uppsättning av $\textstyle n_{1}$ element; sedan $\textstyle k_{2}$ ur en annan uppsättning, och så vidare, genom $\textstyle p$ sådana uppsättningar, tills totalt $\textstyle m$ element har valts från uppsättningarna ${\displaystyle \textstyle p} .$ Man väljer därför $\textstyle m$ element av $\textstyle n_{1}+\dots +n_{p}$ på vänster sida, vilket också är exakt vad som görs på höger sida.

Vandermondes identitet följer också av följande identitet genom att sätta t=0. Givet $p,q,s\leq p+q$ . Sedan för $t\leq s$ :

{p+q+t \choose s}{s \choose t}=\summa _{a+c=s,n\leq a,r\leq c,n+r=t}{p+n \välj a}{a \välj n}{q+r \välj c}{c \välj r}-\summa _{a+c=s-1,n\leq a,r\leq c,n+r =t-1}{p+n \välj a}{a \välj n}{q+r \välj c}{c \välj r}.

Chu–Vandermonde identitet

Identiteten generaliserar till icke-heltalsargument. I det här fallet är den känd som Chu–Vandermonde-identiteten (se Askey 1975, s. 59–60 ) och tar formen

{s+t \choose n}=\summa _{k=0}^{n}{s \choose k }{t \choose nk}

för allmänt komplext värderade s och t och alla icke-negativa heltal n . Det kan bevisas i linje med det algebraiska beviset ovan genom att multiplicera binomialserien för $(1+x)^{s}$ och $x)^{t}}$ ${\displaystyle (1+$ ) och jämför termer med binomialserien för $(1+x)^{s+t}$ .

Denna identitet kan skrivas om i termer av de fallande Pochhammer-symbolerna som

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

i vilken form den tydligt känns igen som en umbral variant av binomialsatsen (för mer om umbralvarianter av binomialsatsen, se binomialtyp ). Chu–Vandermonde-identiteten kan också ses som ett specialfall av Gauss hypergeometriska sats , som säger att

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

där $\;_{2}F_{1}$ är den hypergeometriska funktionen och $\Gamma (n+1)=n!$ är gammafunktionen . Man återtar Chu–Vandermonde-identiteten genom att ta a = − n och tillämpa identiteten

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

frikostigt.

Rothe -Hagen-identiteten är en ytterligare generalisering av denna identitet.

Den hypergeometriska sannolikhetsfördelningen

När båda sidor har dividerats med uttrycket till vänster, så att summan blir 1, kan summans termer tolkas som sannolikheter. Den resulterande sannolikhetsfördelningen är den hypergeometriska fördelningen . Det är sannolikhetsfördelningen av antalet röda kulor i r drag utan ersättning från en urna som innehåller n röda och m blå kulor.

Se även