o-mathe | Anzahl von Auswahlmöglichkeiten » Zusammenfassung

Zusammenfassung - Auswahlmöglichkeiten

Eine Auswahl treffen

Beim Lotto „ $6$ aus $49$ “ werden $6$ Zahlen aus dem Bereich $1 . . . 49$ gezogen. Dabei kommt es nicht auf die Reihenfolge an, in der die Zahlen gezogen werden.

Hier wird von einer Auswahl (von $6$ Zahlen aus den vorgegebenen Zahlen $1 . . . 49$ ) gesprochen.

Bei einer Auswahl wird eine bestimmte Anzahl von Objekten aus einer Gesamtheit von unterscheidbaren Objekten entnommen. Dabei spielt die Reihenfolge, in der die Objekte entnommen werden, keine Rolle.

Beachte, dass wir hier nur unterscheidbare Objekte (wie z. B. nummerierte oder verschiedenfarbige Kugeln) betrachten.

Solche Auswahlen kommen im Alltag häufig vor. Hier einige Beispiele:

Auswahl von $11$ Spieler(innen) aus einer Gesamtheit von $25$ Spieler(innen)
Auswahl von $4$ Karten aus einem Kartenspiel mit $32$ Karten
Auswahl von $2$ Büchern aus einer Vorschlagsliste mit $10$ Büchern

Die Anzahl von Auswahlmöglichkeiten bestimmen

Jede Auswahl kann mit einem Urnenexperiment (mit durchnummerierten Kugeln) ohne Zurücklegen der Kugeln und ohne Berücksichtigung der Reihenfolge der gezogenen Kugeln simuliert werden. Es reicht daher, wenn wir im Folgenden nur Urnenziehungen betrachten.

Als Beispiel betrachten wir die Urnenziehung „ $3$ aus $8$ “. Hier werden $3$ Kugeln aus einer Urne mit $8$ durchnummerierten Kugeln ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge gezogen.

Die Anzahl der Auswahlmöglichkeiten bestimmen wir, indem

wir von der Anzahl der möglichen Anordnungen beim Ziehen ohne Zurücklegen mit Berücksichtigung der Reihenfolge ausgehen
und dann durch die Anzahl der Permutationen einer Anordnung (die alle zur selben Auswahl führen) dividieren.

Für die Anzahl $N$ der verschiedenen Auswahlmöglichkeiten bei der Urnenziehung „ $3$ aus $8$ “ gilt somit:

$N = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1}$

Die Überlegungen zur Urnenziehung „ $3$ aus $8$ “ lassen sich auf analoge Ziehungen wie folgt verallgemeinern:

Bei der Urnenziehung „ $k$ aus $n$ “ werden $k$ Kugeln aus einer Urne mit $n$ durchnummerierten Kugeln ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge ausgewählt. Für die Anzahl $N$ der verschiedenen Auswahlmöglichkeiten gilt:

$N = \frac{\overset{k Faktoren}{\overset{⏞}{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}}}{\underset{k Faktoren}{\underset{⏟}{k \cdot (k - 1) \cdot \dots \cdot 1}}}$

Binomialkoeffizienten bei der Beschreibung verwenden

Für Quotienten aus Produkten absteigender natürlicher Zahlen wird eine Kurzschreibweise verwendet:

$(\begin{matrix} 8 \\ 3 \end{matrix}) = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1}$ (gelesen: „ $8$ über $3$ “)

Verallgemeinernd wird diese Schreibweise wie folgt festgelegt:

Mit $(\begin{matrix} n \\ k \end{matrix})$ (gelesen: „ $n$ über $k$ “) wird ein Quotient bestehend aus Produkten von natürlichen Zahlen beschrieben. Hierbei sind $k$ und $n$ zwei natürliche Zahlen mit $k \leq n$ .

Beispiel:

$(\begin{matrix} 8 \\ 3 \end{matrix}) = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1}$

Allgemein:

$(\begin{matrix} n \\ k \end{matrix}) = \frac{\overset{k Faktoren}{\overset{⏞}{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}}}{\underset{k Faktoren}{\underset{⏟}{k \cdot (k - 1) \cdot \dots \cdot 1}}}$

Solche Ausdrücke werden Binomialkoeffizienten genannt.

Für den Fall $k = 0$ ist der Binomialkoeffizient so festgelegt:

$(\begin{matrix} n \\ 0 \end{matrix}) = 1$

Auf Taschenrechnern ist oft eine Taste mit der Aufschrift [nCr] (für „ $n$ choose $r$ “) zur Berechnung von Binomialkoeffitienten vorhanden.

Binomialkoeffizienten lassen sich gut mit Hilfe eines Gitternetzes verdeutlichen.

Anleitung für das Applet

Im oberen Auswahlblock kannst du die Felder anklicken und somit eine Auswahl an roten Feldern erzeugen.
Den hervorgehobenen blauen Punkt kannst du unten im Gitternetz bewegen.
Die Anzahl der (kürzesten) Wege im dargestellten Gitternetz vom Startpunkt ganz oben bis zu einem Gitterpunkt kann mit geeigneten Binomialkoeffizienten beschrieben und somit auch berechnet werden. Im Applet werden die zu den Punkten zugehörigen Binomialkoeffizienten angezeigt.

Zum Herunterladen: wegeimgitternetz3.ggb

Eigenschaften des Binomialkoeffizienten beschreiben

Binomialkoeffizienten lassen sich mit Hilfe von Fakultäten beschreiben.

$(\begin{matrix} 8 \\ 3 \end{matrix}) = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{8!}{3! \cdot 5!}$

Allgemein gilt:

$(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!}$

Beachte, dass bei der Berechnung von Fakultäten sehr große Zahlen entstehen. Daher wird die Darstellung von Binomialkoeffizienten mit Hilfe von Fakultäten normalerweise nicht zur Berechnung der Binomialkoeffizienten verwendet. Sie kann aber gut genutzen werden, um z. B. folgende Eigenschaft von Binomialkoeffizienten direkt zu begründen:

$(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$

Anzahl der Auswahlmöglichkeiten beschreiben

Die Anzahl der Auswahlmöglichkeiten kann mit den neuen Darstellungen und Erkenntnissen nun wie folgt beschrieben werden:

$N = (\begin{matrix} n \\ k \end{matrix}) = \frac{\overset{k Faktoren}{\overset{⏞}{n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)}}}{\underset{k Faktoren}{\underset{⏟}{k \cdot (k - 1) \cdot \dots \cdot 1}}} = \frac{n!}{k! \cdot (n - k)!}$