Kombinatorischer Beweis von ∑i=0m2n−i(ni)(mi)=∑i=0m(n+m−im)(ni)∑i=0m2n−i(ni)(mi)=∑i=0m(n+). m−im)(ni) \sum \limits_{i = 0} ^{m} 2^{ni} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m { n + m - ich \choose m} {n \choose i}

Du hast$n$Frauen in einem Raum und$m$Männer in einem anderen. Sie wählen insgesamt aus$m$Menschen aus den gemeinsamen Bewohnern der beiden Räume und schicken sie zu einer Vorlesung über Kombinatorik. Dann wählst du eine Untergruppe der verbleibenden Frauen aus und schickst sie zu einer Vorlesung über Topologie und schickst alle anderen nach Hause. Lassen$i$sei die Zahl der Frauen, die zur Vorlesung über Kombinatorik geschickt werden; dann gibt es$\binom{n}i\binom{m}{m-i}2^{n-i}=\binom{n}i\binom{m}i2^{n-i}$Möglichkeiten, die Auswahl zu treffen, so ist die Gesamtzahl der Möglichkeiten

$$\sum_{i=0}^m\binom{n}i\binom{m}i2^{n-i}\;.$$

Alternativ könnten Sie auswählen$i$Frauen nach Hause geschickt werden, und dann aus den verbleibenden Bewohnern der beiden Zimmer auswählen$m$Besuch der Kombinatorik-Vorlesung; Der Rest$n-i$Frauen besuchen die Topologie-Vorlesung. Das kann man natürlich machen

$$\sum_{i=0}^n\binom{n}i\binom{n+m-i}m$$

Wege. (Beachten Sie, dass$i$kann so viel sein wie$n$bei diesem ansatz sollte also die summe haben$n$als Obergrenze.) Jede Prozedur sendet$m$Personen in die Kombinatorik-Vorlesung und eine Untergruppe der restlichen Frauen in die Topologie-Vorlesung, und jede erlaubt jede mögliche Zuordnung dieser Art, also zählen sie dasselbe.

Lassen$A,B$disjunkt sein mit$|A|=n$Und$|B|=m$.

Auf der linken Seite ersetzen$\binom{m}{i}=\binom{m}{m-i}$.

Lassen

$$T=\left\{(C_1,C_2)\mid C_1\subseteq A\cup B, C_2\subseteq A, |C_1|=m, C_1\cap C_2=\emptyset\right\}$$

Definieren$f,g:T\to \mathbb N$von:

$$\begin{align} f&:(C_1,C_2)\mapsto |C_1\cap A|\\ g&:(C_1,C_2)\mapsto |C_2| \end{align}$$

Der

$$|T|=\sum_{i=0}^{\infty} \left|f^{-1}(i)\right| = \sum_{i=0}^{\infty} \left|g^{-1}(i)\right|$$

Jetzt,$f^{-1}(i)$kann durch Pflücken gezählt werden$i$Elemente von$A$Und$m-i$Elemente von$B$zu bekommen$C_1$, und dann eine beliebige Teilmenge der verbleibenden$n-i$Elemente von$A$zu bekommen$C_2$. So

$$\left|f^{-1}(i)\right| = 2^{n-i}\binom{n}{i}\binom{m}{m-i}$$

Und$g^{-1}(i)$kann durch Pflücken gezählt werden$i$Elemente von$A$für$C_2$, und dann irgendwelche$m$Elemente der verbleibenden$m+n-i$Elemente von$A\cup B$zu bekommen$C_1$. So

$$\left|g^{-1}(i)\right|= \binom{n}{i}\binom{n+m-i}{m}$$

Schließlich zählt das für$f^{-1}$Null sind, wenn$i>m$und die Zählung für$g^{-1}$sind ero für$i>n$, um meinen obigen Kommentar zu unterstützen, dass die Frage korrigiert werden muss$\sum_{i=0}^n$rechts nicht$\sum_{i=0}^m$.

Erlauben Sie mir zu bemerken, dass es auch einen einfachen algebraischen Beweis gibt. Beachten Sie die Korrektur in der oberen Grenze der RHS.

Angenommen, wir versuchen das zu zeigen

$$\sum_{q=0}^m {m\choose q} 2^{n-q} {n\choose q} = \sum_{q=0}^n {n+m-q\choose m} {n\choose q}$$ Wo$n\ge m.$

Führen Sie die Integraldarstellung ein

$${n\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{q+1}}\; dz$$

was für die LHS gibt

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \sum_{q=0}^m {m\choose q} \frac{1}{(2z)^{q}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \left(1+\frac{1}{2z}\right)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^{n-m}\times (1+z)^n}{z^{m+1}} (1+2z)^m \; dz.$$

Führen Sie für die RHS die Integraldarstellung ein

$${n+m-q\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m-q}}{z^{m+1}}\; dz$$

was für die RHS gibt

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \sum_{q=0}^n {n\choose q} \frac{1}{(1+z)^q}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \left(1+\frac{1}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{m+1}} (2+z)^n \; dz.$$

Jetzt setzen$z=2w$erhalten

$$\frac{1}{2\pi i} \int_{|w|=\epsilon/2} \frac{(1+2w)^{m}}{(2w)^{m+1}} (2+2w)^n \; 2 \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon/2} 2^{n-m} \frac{(1+2w)^{m}}{w^{m+1}} (1+w)^n \; dw.$$

Das entspricht dem Integral für die linke Seite, fertig.

Anmerkung. Es ist nicht schwierig, Koeffizienten aus diesem Integral zu extrahieren, aber das ist nicht notwendig, da die Gleichheit der beiden Integrale ausreichend ist (beachten Sie auch, dass alle beteiligten Summen endlich sind).