Zeige mit kombinatorischen Argumenten Aussagen zu Summen von Binomialkoeffizienten: Bsp.(2n tief 2) = 2(ntief2) + n^2

Question

Zeigen Sie mit kombinatorischen Argumenten folgende Aussagen:

(a) Für alle \( n \in \mathbb{N} \) gilt \( \sum \limits_{j=0}^{n}\left(\begin{array}{l}{n} \\ {j}\end{array}\right)=2^{n} \)

(b) Für alle \( n \in \mathbb{N}_{+} \) gilt \( \left(\begin{array}{c}{2 n} \\ {2}\end{array}\right)=2\left(\begin{array}{l}{n} \\ {2}\end{array}\right)+n^{2} \)

(c) Für alle \( n \in \mathbb{N}_{+} \) und \( 0 \leq k<n \) gilt \( \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\sum \limits_{j=0}^{k}\left(\begin{array}{c}{n-1-j} \\ {k-j}\end{array}\right) \)

(d) Für alle \( n \in \mathbb{N}_{+} \) und \( 0<k \leq n \) gilt \( \left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\sum \limits_{j=0}^{n-k}\left(\begin{array}{c}{n-1-j} \\ {k-1}\end{array}\right) \)

(e) Für alle \( n, m \in \mathbb{N} \) und \( m \leq n \) gilt \( \sum \limits_{k=0}^{m}\left(\begin{array}{l} {n} \\ {k} \end{array}\right)\left(\begin{array}{l} {n-k} \\ {m-k} \end{array}\right)=2^{m}\left(\begin{array}{l} {n} \\ {m} \end{array}\right) \)

Zeilensumme im Pascaldreieck. Binomialkoeffizienten. Fakultäten kürzen.

Answer 1

Vorweg: Wenn man dasselbe auf 2 Arten berechnet, hat man einen kombinatorischen Beweis einer Aussage geführt. Damit du weisst, was kombinatorische Argumente sein können, hier mal die a)

(a) (n tief j) ist die Anzahl der j-elementigen Teilmengen einer n-elementigen Menge M.

Nun wird links vom Gleichheitszeichen die Zahl der 0-elementigen, 1-elementigen, 2-elementigen…n-elementigen Teilmengen addiert. Das gibt die Zahl aller möglichen Teilmengen von M.

Diese Zahl kann man auch direkt berechnen: man entscheidet bei jedem Element, ob es zur Teilmenge gehört oder nicht: Jeweils 2 Möglichkeiten. Deshalb 2*2*2… n Faktoren. Also 2^n.

Übrigens ist das die Zeilensumme im Pascaldreieck.

(b) ( 2n tief 2) steht für die Zahl der 2-elementigen Teilmengen einer Menge M mit 2n Elementen.

Diese Zahl kann man auch berechnen, indem man zuerst die M in zwei n-elementige Menge M1 und M2 unterteilt. M1 hat selbst (n tief 2) 2-elementige Teilmengen. M2 ebenfalls. Wenn man wieder an die Gesamtzahl der 2-elementigen Teilmengen von M denkt, kann man rechnen (n tief 2) + (n tief 2) + die Zahl der Mengen, die ein Element aus M1 und eines aus M2 enthalten. 
Der letzte Summand ist n*n, da M1 und M2 je n Elemente enthalten.

Also: (2n tief 2) = 2*(n tief 2) + n^2.

 

 

(e) links: (n tief 0)(n tief m) + (n tief 1)(n-1 tief m-1)) + (n tief 2)(n-2 tief m-2)+…+(n tief m)(n-m tief 0)

Summe einer Anzahl Zweierabfolgen 1.,2.,3. …m+1. von Teilmengen einer Menge M mit n Elementen, die zusammen jeweils m verschiedene Elemente von M enthalten.
Interpretation der Summanden in Text:

1. Zuerst o-elementige Menge. Dann aus den restlichen n Elementen m auswählen.

2. Zuerst 1-elementige Menge. Dann aus den restlichen n-1 Elementen m-1 auswählen.

3. Zuerst 2- elementige Menge. Dann aus den restlichen n-2 Elementen m-2 auswählen.

…

m+1. Zuerst m-elementige Menge. Dann aus den restlichen n-m Elementen keines mehr auswählen.

rechts: 2^m * (n tief m)

= (n tief m) * 2^n

Kombinatorische Interpretation der Rechnung

Zuerst aus der Menge M m Elemente auswählen: (n tief m) Möglichkeiten.

Dann für jedes dieser m gewählten Elemente enscheiden, ob es in die erste oder 2. Teilgruppe gehört: Nacheinander immer 2 Möglichkeiten. Deshalb 2^m.

Ergibt total die oben blau beschriebene Anzahl von Mengen. qed durch kombinatorische Argumentation.

Ich hoffe du kommst jetzt auch bei den folgenden Teilaufgaben klar. Die formale Anpassung an die Darstellung in deinen Unterlagen ist ebenfalls dir überlassen.

 

Comments

Ich hänge bei der gleichen Aufgabe, aber mein Problem sind nicht die kombinatorischen Argumente, sondern dass ich nicht versteh warum. Mit deiner Erklärung versteh ich jetzt die a und die b, aber ich komm bei den anderen 3 leider nicht selber drauf...

---

n tief k ist die Anzahl aller k-elementigen Mengen einer n-elementigen Menge.

rechts vom GLEICH

steht (n-1 tief k) + (n-2 tief k-2) + (n-3 tief k-2) + … + (n-1-k tief 0). BEACHTE hier k<n.

Seien die n Elemente von 1 bis n nummeriert.

1,2,3,4,5,6,7,,8,…, n-3,n-2,n-1,n

nun kann eine k-elementige Teilmengen

1. aus den ersten n-1 Elementen zusammengesetzt sein.

Das geht auf (n-1 tief k) Arten.

oder sie enthält das Element Nr. n.

Also kann man folgende Fälle addieren (Zusammenhängende Ketten von rechts wachsen lassen bis das maximal zusammenhängende rechts in der Elementanordnung noch gewählt wurde)

2. (Falls k > 0) Alle Mengen, die das Element Nr. n enthalten (eine Mögl.) und Nr. n-1 nicht enthalten:

(n-2 tief k-1) Mögl. :die Zahl der k-1 elementigen Teilemengen der ersten n-2 Elemente

Also: (n-2 tief k-1)*1 =(n-2 tief k-1)

3. (Falls k auch >1)  Alle Mengen, die die Element Nr. n und n-1 enthalten (eine Mögl.) und Nr. n-2 nicht enthalten:

(n-3 tief k-2) Mögl. :die Zahl der k-2 elementigen Teilmengen der ersten n-3 Elemente

Also: (n-3 tief k-2)*1= (n-3 tief k-2)

 

4. (Falls k auch >2)  Alle Mengen, die die Element Nr. n, n-1, n-2 enthalten (eine Mögl) und Nr. n-3 nicht enthalten:

(n-4 tief k-3) Mögl. :die Zahl der k-2 elementigen Teilmengen der ersten n-3 Elemente

Also: (n-4 tief k-3)*1 =(n-4 tief k-3)

…

?. Die Menge, die die Element Nr. n und n-1, n-2 bis n-k+1 enthält, Nr n-k nicht enthält und auch kein vorheriges Element enthält:

(n-k-1 tief 0) Mögl. :die Zahl der k-2 elementigen Teilemengen der ersten n-3 Elemente

Also: (n-k-1 tief 0)*1 =(n-k-1 tief 0)

 

Nun das Ganze noch schön zusammenfassen mit Summenzeichen etc. qed. c)

Ich hoffe jetzt mal, du findest für d) und e) eine eigene Erklärung. 

Beachte bei d, dass k>0. Du dürftest deshalb bei der Summierung mit einem ausgezeichneten Element starten, das zur Teilmenge gehört.