Malle Mathematik verstehen 7, Schulbuch

221 9.7 Kombinatorische Abzählformeln und hypergeometrische Verteilung Jede Stern-Strich-Folge besteht aus 15 Symbolen (7 Sternen und 8 Strichen). Sie ist durch die Angabe der Positionen für die 8 Striche vollkommen bestimmt (denn an den restlichen Positionen stehen automatisch die 7 Sterne). Die Positionen der 8 Striche können aus den 15 möglichen Positionen auf ​ 2  ​ 15  8 ​  3 ​Arten ausgewählt werden. Also gibt es ​ 2  ​ 15  8 ​  3 ​= 6435 Stern-Strich- Folgen und somit gibt es auch 6435 mögliche Auswahlen. b) Wir stellen jede Auswahl von k Zahlen durch ein k-Tupel dar, dessen Elemente der Größe nach geordnet sind. Jedes k-Tupel kann als Stern-Strich-Folge mit n + k – 1 Symbolen (k Sternen und n – 1 Strichen) dargestellt werden. Da es ​ 2  ​ n + k – 1  k  ​  3 ​solcher Stern-Strich-Folgen gibt, gibt es auch ​ 2  ​ n + k – 1  k  ​  3 ​mögliche Auswahlen. Geordnete Auswahlen 9.140 Geordnete Auswahl ohne Wiederholung: Auf wie viele Arten kann man mit Berücksichtigung der Reihenfolge  a) aus der Menge M = {1, 2, 3, 4, 5} drei Zahlen,  b) aus der Menge M = {1, 2, 3, …, n} k Zahlen auswählen, wenn keine Wiederholungen zugelassen sind? Lösung: a) Für die erste Zahl gibt es 5 Möglichkeiten, für die zweite Zahl nur mehr 4 Möglichkeiten und für die dritte Zahl nur mehr 3 Möglichkeiten. Insgesamt gibt es also 5·4·3 = 60 mögliche Auswahlen. b) Für die erste Zahl gibt es n Möglichkeiten, für die zweite Zahl nur mehr n – 1 Möglichkeiten, für dritte Zahl nur mehr n – 2 Möglichkeiten, … für die k-te Zahl nur mehr n – (k – 1) = n – k + 1 Möglichkeiten. Insgesamt gibt es also n · (n – 1) · (n – 2) ·…· (n – k + 1) mögliche Auswahlen. 9.141 Geordnete Auswahl mit Wiederholung: Bei der von Louis Braille erfundenen Blindenschrift werden Zeichen in einem rechteckigen 3×2-Punktraster durch tastbare Erhebungen dargestellt, wobei wenigstens eine Erhebung vorhanden sein muss. 1) Wie viele Zeichen können auf diese Weise codiert werden? 2) Für die Arbeit am Computer wird ein umfangreicherer Zeichensatz benötigt. Bei der Computer-Brailleschrift wird dazu ein 4×2-Punktraster verwendet. Wie viele Zeichen können so unterschieden werden? Lösung: 1) Wir bezeichnen einen erhobenen Tastpunkt mit e und einen nicht erhobenen mit n. Gehen wir die Tastpunkte zeilenweise durch, entspricht jede Anordnung einer geordneten Auswahl von 6 Elementen aus der Menge {e, n}, wobei Wiederholungen zugelassen sind. Für das erste Element gibt es 2 Möglichkeiten, für das zweite ebenfalls 2 Möglichkeiten, … für das letzte Element ebenfalls 2 Möglichkeiten. Insgesamt gibt es 2 · 2 ·…· 2 = 2 6 = 64 Auswahlen. Da aber nicht alle ausgewählten Elemente gleich n sein dürfen, gibt es nur 64 – 1 = 63 Zeichen. 2) Jede Anordnung entspricht einer geordneten Auswahl von 8 Elementen aus der Menge {e, n}, wobei Wiederholungen zugelassen sind. Für jedes Element gibt es 2 Möglichkeiten. Insgesamt können also 2 8 – 1 = 255 Zeichen unterschieden werden. Beispiel: T Nur zu Prüfzwecken – Eigentum des Verlags öbv