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! } \)
