Rekursive Darstellung des Binomialkoeffizienten?

...komplette Frage anzeigen

1 Antwort

(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.



Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?