Malle Mathematik verstehen 7, Schulbuch

203 9.4 Fakultät und Binomialkoeffizienten Binomialkoeffizienten 9.63 Wie viele zweielementige Teilmengen enthält die vierelementige Menge {a, b, c, d}? 1. Lösungsmöglichkeit: Es gibt sechs zweielementige Teilmengen der Menge a, b, c, d, die wir lexikografisch geordnet angeben: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} Beachte dabei, dass es nicht darauf ankommt, in welcher Reihenfolge die Elemente einer Menge angeschrieben werden. Es gilt beispielsweise {a, b} = {b, a}. 2. Lösungsmöglichkeit: Wir wählen die beiden Elemente für eine zweielementige Teilmenge der Reihe nach aus. Für das erste Element gibt es 4 Möglichkeiten, für das zweite Element nur mehr 3 Möglichkeiten. Insgesamt gibt es nach der Produktregel also 4 · 3 = 12 Möglichkeiten zwei Elemente auszuwählen. Dabei liefern jedoch jene Auswahlen, die sich nur in der Reihenfolge der ausgewählten Elemente unterscheiden, dieselbe Teilmenge (zum Beispiel ab und ba). Die Anzahl aller zweielementigen Teilmengen beträgt somit:   12 _ 2  = 6 9.64 Wie viele k-elementige Teilmengen enthält eine n-elementige Menge? Lösung: Wir wählen die Elemente für eine k-elementige Teilmenge der Reihe nach aus. Für das erste Ele- ment gibt es n Möglichkeiten, für das zweite Element nur mehr n – 1 Möglichkeiten, für das dritte Element nur mehr n – 2 Möglichkeiten, … , für das k-te Element nur mehr n – (k – 1) = n – k + 1 Möglichkeiten. Insgesamt gibt es nach der Produktregel also n · (n – 1) · (n – 2) ·…· (n – k + 1) Möglichkeiten, k Elemente auszuwählen. Dabei liefern jedoch die k! Auswahlen, die sich nur in der Reihenfolge der ausgewählten Elemente unterscheiden, dieselbe k-elementige Teilmenge. Die Anzahl aller k-elementigen Teilmengen beträgt somit:   n · (n – 1) · (n – 2) ·…· (n – k + 1) _____  k!  =   n · (n – 1) · (n – 2) ·…· (n – k + 1) _____   k · (k – 1) · (k – 2) ·…· 1  Zur Abkürzung führt man folgende Schreib- und Sprechweisen ein: Definition Binomialkoeffizienten: Für n, k * N * mit k ª n setzt man: 2    n k   3 =   n · (n – 1) · (n – 2) ·…· (n – k + 1) _____   k · (k – 1) · (k – 2) ·…· 1  =   n! __  k!(n – k)! [sprich: n über k] Ergänzend setzt man: 2    n 0   3 = 1 Die Zahlen 2    n k   3 nennt man Binomialkoeffizienten . Damit kann das Ergebnis aus Aufgabe 9.64 so formuliert werden: Satz 2    n k   3 ist gleich der Anzahl der k-elementigen Teilmengen einer n-elementigen Menge. Beispiel: Die Anzahl der 3-elementigen Teilmengen einer 9-elementigen Menge beträgt: 2  9    3 3 =   9 · 8 · 7 __  3 · 2 · 1 = 84 Bemerkung: Man setzt 2   n  0   3 = 1, da eine n-elementige Menge genau eine 0-elementige Teilmenge besitzt, nämlich die leere Menge. Nur zu Prüfzwecken – Eigentum des Verlags öbv