Frage von kimchikimchi, 22

Rekursive Darstellung des Binomialkoeffizienten?

Könnte mir jemand die Rekursive Darstellung des Binomialkoeffizienten erklären? Es soll ja (n+1 über k+1)= (n über k)+ (n über k+1). Es wird also zu n ein Objekt hinzugefügen, daraus sollen k+1 Objekte ausgewählt werden. Es gibt nun 2 mögliche Fälle: 1. Das neue Objekt wird ausgewählt, nun müssen aus der Menge n nur noch k Objekte ausgewählt werden. Die Möglichkeiten betragen also (n über k). (Das verstehe ich noch). 2. Das neue Objekt wird nicht ausgewählt. Es müssen dann noch k+1 Objekte aus der Menge n ausgewählt werden(aber weshalb, es wurde doch 1 Objekt bereits entfernt, müsste man dann nicht nur noch k Objekte wegnehmen?).Und was bedeutet die rekursive Darstellung überhaupt genau? Vielen Dank im Voraus!

Antwort
von Schachpapa, 10

(n über k) sei die Anzahl k-elementiger Teilmengen aus n Elementen.

Nehmen wir eine n-elementige Grundmenge an. Ich nehme ein bestimmtes Element x weg.

Dann gibt es (n-1 über k-1) Teilmengen mit (k-1) Elementen und
(n-1 über k) Teilmengen mit k Elementen.

Wenn ich zur ersten Gruppe jeweils das vorher weggenommene x hinzufüge, habe ich insgesamt (n-1 über k-1) k-elementige Teilmengen, die x enthalten und
(n-1 über k) k-elementige Teilmengen, die x nicht enthalten.

Die Anzahl der k-elementigen Teilmengen aus n Elementen ist also 
(n-1 über k-1) + (n-1 über k)

Dies rekursive Darstellung bedeutet, dass du den Binomialkoeffizienten als Summe zweier Binomialkoeffizienten mit kleinerem n berechnen kannst.

Vgl. Pascalsches Dreieck

Mir fällt gerade auf, dass es bei dir heißt:

(n+1 über k+1)= (n über k)+ (n über k+1)

Ich hoffe, du erkennst, dass das das gleiche ist wie :

(n über k) = (n-1 über k-1) + (n-1 über k)

nur mit anderem Bezugspunkt.



Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten