+1 Daumen
1,5k Aufrufe

Aufgabe:

Eine fundamentale Eigenschaft der Binomialkoeffizienten ist die Identität \( \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\left(\begin{array}{c}{n} \\ {n-k}\end{array}\right) \) für alle \( n, k \in \mathbb{N} \) mit \( 0 \leq k \leq n \).

a) Beweisen Sie diese Identität an Hand der geschlossenen Formel.

b) Führen Sie einen kombinatorischen Beweis dieser Identität durch Konstruktion einer Bijektion (zwischen welchen Mengen?).

c) Beweisen Sie, dass \( \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\left(\begin{array}{c}{n-1} \\ {n-k}\end{array}\right) + \left(\begin{array}{c}{n-2} \\ {n-k-1}\end{array}\right)+\left(\begin{array}{c}{n-2} \\ {n-k-2}\end{array}\right) \) für beliebige \( n \geq 3 \) und \( 1 \leq k \leq n-2 \) gilt.

von

1 Antwort

0 Daumen

Bei a)

Forme ich die rechte Seite zur linken um:

\( \left(\begin{array}{c}{n} \\ {n-k}\end{array}\right)=\frac{n !}{(n-k) !(n-(n-k)) !}= \)

\( \frac{n !}{(n-k) !(n-n+k) !}=\frac{n !}{(n-k) ! k !}=\left(\begin{array}{c}{n} \\ {k}\end{array}\right) \)

Zu b)

'n tief k' bezeichnet die Menge der k-elementigen Teilmengen einer n-elementigen Menge

'n tief (n-k)' bezeichnet die Menge der (n-k)-elementigen Teilmengen einer n-elementigen Menge

Die gefragte bijektive Zuordnung ist die Zuordnung, die jeder Teilmenge der gegebenen n-elementigen Menge ihre Komplementärmenge zuordnet.

Kombinatorische Erklärung zu c) ermöglicht folgende Kurzvereinfachung:

Begründung: Man gelangt im Pascaldreieck von einer Zeile auf die nächste, indem man 2 aufeinanderfolgende Koeffizienten der oberen Zeile addiert. Die neue Nr. ist immer die grössere der beiden, da das Pascaldreieck nach unten wächst.

Kombinatorische Erklärung dieses Schrittes: Die Zahl der x+1- elementigen Teilmengen einer m+1-elementigen Menge entspricht, der Zahl aller dieser Mengen, die das m+Erste Element enthalten und nur x Elemente aus dern ersten m Elementen plus der Zahl, die das m+ Erste nicht enthalten, dafür x+1 Elemente aus den ersten m Elementen. Deshalb gilt formal: ((m+1) tief (x+1) = 1*(m tief x) + 1*(m tief (x+1))

Also kann man erst den 2. und den 3. Summanden rechts zusammennehmen:

Entspricht Schritt von Zeile n-2 nach Zeile n-1 ist die grössere 'Tiefzahl' nachher n-k-1

Dann die beiden verbleibenden Summanden: Schritt von Zeile n-1 nach Zeile n

Linke Seite  \( \left(\begin{array}{c}{n} \\ {k}\end{array}\right)=\left(\begin{array}{c}{n} \\ {n-k}\end{array}\right) \)
Rechte Seite \( \left(\begin{array}{c}{n-1} \\ {n-k}\end{array}\right)+\left(\begin{array}{c}{n-2} \\ {n-k-1}\end{array}\right)+\left(\begin{array}{c}{n-2} \\ {n-k-2}\end{array}\right)= \)
\( \left(\begin{array}{c}{n-1} \\ {n-k}\end{array}\right)+\left(\begin{array}{c}{n-1} \\ {n-k-1}\end{array}\right) = \left(\begin{array}{c}{n} \\ {n-k}\end{array}\right) \)

Zu c) Die formale Umformung stimmt so noch nicht: Vielleicht will das jemand noch ändern?

\( \text{Rechte Seite } \left( \begin{matrix} n-1 \\ n-k \end{matrix} \right) +\left( \begin{matrix} n-2 \\ n-k-1 \end{matrix} \right) +\left( \begin{matrix} n-2 \\ n-k-2 \end{matrix} \right) =\\ \\ \left( \begin{matrix} n-1 \\ n-1-(k+1) \end{matrix} \right) +\left( \begin{matrix} n-2 \\ n-2-(k+1) \end{matrix} \right) +\left( \begin{matrix} n-2 \\ n-2-k \end{matrix} \right) =\\ \left( \begin{matrix} n-1 \\ k+1 \end{matrix} \right) +\left( \begin{matrix} n-2 \\ k+1 \end{matrix} \right) +\left( \begin{matrix} n-2 \\ k \end{matrix} \right) =\\ \quad \frac { (n-1)! }{ (k+1)!(n-1-(k+1))! } +\quad \frac { (n-2)! }{ (k+1)!(n-2-(k+1))! } +\frac { (n-2)! }{ k!(n-2-k)! } =\\ \frac { (n-1)(n-2)! }{ (k+1)!(n-2-k)! } +\quad \frac { (n-2-k)(n-2)! }{ (k+1)!(n-2-k)(n-3-k)! } +\frac { (n-2)! }{ k!(n-2-k)! } =\\ \quad \frac { ((n-1)+(n-2-k))(n-2)! }{ (k+1)!(n-2-k)! } +\frac { (n-2)! }{ k!(n-2-k)! } =\\ \frac { (2n-3-k)(n-2)! }{ (k+1)!(n-2-k)! } +\frac { (k+1)(n-2)! }{ (k+1)k!(n-2-k)! } =\\ \frac { (2n-3-k+k+1)(n-2)! }{ (k+1)!(n-2-k)! } =\\ \frac { (2n-2)(n-2)! }{ (k+1)!(n-2-k)! } =\frac { 2(n-1)(n-2)! }{ (k+1)!(n-2-k)! } =\frac { 2(n-1)! }{ (k+1)!(n-1-(k+1))! } \)

Das stimmt noch nicht ganz.

Es wäre \( 2 · \left( \begin{matrix} n-1 \\ k+1 \end{matrix} \right) \\ \\ \\ \\ \frac { (n-1)! }{ (k+1)!(n-2-k)! } +\quad \frac { (n-2)! }{ (k+1)!(n-3-k)! } +\frac { (n-2)! }{ k!(n-2-k)! } =\\ \\ \\ \\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (n-2)! }{ (n-k-1)!(k-1)! } +\frac { (n-2)! }{ (n-k-2)!k! } =\\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (n-2)! }{ (n-k-1)!(k-1)! } +\frac { (n-k-1)(n-2)! }{ (n-k-1)(n-k-2)!k! } =\\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (n-2)! }{ (n-k-1)!(k-1)! } +\frac { (n-k-1)(n-2)! }{ (n-k-1)!k! } =\\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (n-2)!+(n-k-1)(n-2)! }{ (n-k-1)!(k-1)! } =\\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (1+n-k-1)(n-2)! }{ (n-k-1)!(k-1)! } =\\ \frac { (n-1)! }{ (n-k)!(k-1)! } +\quad \frac { (n-k)(n-2)! }{ (n-k-1)!(k-1)! } =\\ \frac { (n-1)!*k }{ (n-k)!(k-1)!*k } +\quad \frac { (n-k)(n-k)(n-2)!*k }{ (n-k)(n-k-1)!(k-1)!*k } =\\ \frac { (n-2)!(n-1)*k }{ (n-k)!\quad k! } +\quad \frac { ({ n }^{ 2 }-2kn\quad +\quad { k }^{ 2 })(n-2)!*k }{ (n-k)!\quad k! } =\\ \quad \frac { ((n-1)*k\quad +\quad k*({ n }^{ 2 }-2kn\quad +\quad { k }^{ 2 }))(n-2)! }{ (n-k)!\quad k! } =\\ \frac { (nk-k\quad +\quad k{ n }^{ 2 }-2{ k }^{ 2 }n\quad +\quad { k }^{ 3 }))(n-2)! }{ (n-k)!\quad k! }  \)

von 161 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community