Zusammenfassung - Anordnungsmöglichkeiten
Objekte kombinieren
Es gibt zahlreiche Problemstellungen, bei denen es um Kombinationsmöglichkeiten von Objekten geht. Wir beschäftigen uns hier mit folgender Fragestellung:
Leitfrage
Wie wird bei einem mehrstufigen Entscheidungsprozess die Gesamtanzahl der möglichen Kombinationen der Teilergebnisse bestimmt?
Das folgende Beispiel verdeutlich das Vorgehen anhand eines alltagsnahen Kontexts:
Kleidungsstücke kombinieren
Zum Herunterladen: zaehlverfahren2.ggb
Anleitung für das Applet
- Die jeweilige Anzahl der T-Shirts, Jeans und Sneaker kannst du mit den Schiebereglern einstellen.
- Das Baumdiagramm verdeutlich die sich ergebenden Kombinationsmöglichkeiten.
Mit Hilfe von Baumdiagrammen erhälts du direkt:
Anzahl der Möglichkeiten der 1. Stufe | Anzahl der Möglichkeiten der 2. Stufe | Anzahl der Möglichkeiten der 3. Stufe | Gesamtanzahl der möglichen Ergebnisse |
---|---|---|---|
$3$ | $1$ | $2$ | $6$ |
$5$ | $3$ | $4$ | $60$ |
$1$ | $1$ | $3$ | $3$ |
$n_1$ | $n_2$ | $n_3$ | $N = n_1 \cdot n_2 \cdot n_3$ |
Es ergibt sich somit folgende Regel:
Zählregel:
Wenn es bei einem mehrstufigen Entscheidungsprozess $n_1$ Möglichkeiten für die 1. Entscheidungsstufe, $n_2$ Möglichkeiten für die 2. Entscheidungsstufe und $n_3$ Möglichkeiten für die 3. Entscheidungsstufe gibt, dann gibt es insgesamt $N = n_1 \cdot n_2 \cdot n_3$ Kombinationsmöglichkeiten der jeweiligen Teilentscheidungen.
Urnenmodelle verwenden
Mehrstufige Entscheidungsprozesse lassen sich sehr gut mit Urnenziehungen simulieren. Im Folgenden betrachten wir Urnenmodelle, die immer wieder bei Zählvorgängen benutzt werden können.
Urnen werden immer mit irgendwelchen Gegenständen gefüllt (z.B. Zettel, Kugeln, ...). Wir gehen hier immer davon aus, dass die Gegenstände unterscheidbar sind (z.B. durch die Beschriftung bei Zetteln, durch eine Farbe oder Nummerierung bei Kugeln, ...). Zur Vereinfachung betrachten wir nur Situationen, in denen nummerierte Kugeln in die Urnen gefüllt werden. Die Nummern stehen dabei je nach Kontext für unterschiedlichste Gegenstände.
Zudem beschränken wir uns hier auf Urnenziehungen, bei denen die Reihenfolge der gezogenen Objekte berücksichtigt wird. Im nächsten Kapitel betrachten wir dann Urnenziehungen ohne Berücksichtigung der Reihenfolge.
Die Tabelle verdeutlicht einige wichtige Urnenmodellen anhand konkreter Anwendungssituationen:
Vorgang in der Realität | Simulation mit einem Urnenmodell |
---|---|
Tippschein zum Fußballtoto: Hier wird bei jedem Spiel ein Kreuz gesetzt. |
Ziehen mit Zurücklegen mit Berücksichtigung der Reihenfolge |
Tippschein beim Pferderennen: Hier wird für jeden Platz ein Kreuz gesetzt. |
Ziehen ohne Zurücklegen mit Berücksichtigung der Reihenfolge |
Auslosung einer Reihenfolge: Beim Poetry-Slam-Wettbewerb wird die Reihenfolge der Auftritte der Teilnehmer(innen) ausgelost. |
Ziehen aller Kugeln ohne Zurücklegen mit Berücksichtigung der Reihenfolge |
In allen hier aufgeführten Urnenmodellen wird die Reihenfolge der gezogenen Kugeln berücksichtigt. Mit Hilfe von Urnenziehungen wird dabei jeweils eine Anordnung von Objekten (hier: Kugelnummern) gebildet.
Wir betrachten dabei Urnenmodelle mit Zurücklegen und ohne Zurücklegen der gezogenen Kugeln. Das führt zu Anordnungen mit und ohne Wiederholungen.
Im Urnenmodell 3 werden – anders als im Urnenmodell 2 – alle Kugeln aus der Urne gezogen. Als Ergebnis der Ziehung erhälten wir alle Kugelnummern in einer beliebigen Reihenfolge. Eine solche Anordnung aller betrachteten Objekte wird auch Permutation der Objekte genannt.
Anzahl möglicher Anordnungen
Mit Hilfe der oben beschriebenen Zählregel kann die Anzahl möglicher Anordnungen (bzw. Ziehungsergebnisse) bei den betrachteten Urnenmodellen direkt bestimmt werden.
Urnenmodell | Anzahl der möglichen Ziehungen (Anordnungen) |
---|---|
Ziehen mit Zurücklegen mit Berücksichtigung der Reihenfolge |
Anzahl der möglichen Teilergebnisse: 1. Ziehung: $3$ 2. Ziehung: $3$ ... 6. Ziehung: $3$ Gesamtanzahl der möglichen Ergebnisse: $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 3^6$ |
Ziehen ohne Zurücklegen mit Berücksichtigung der Reihenfolge |
Anzahl der möglichen Teilergebnisse: 1. Ziehung: $9$ 2. Ziehung: $8$ 3. Ziehung: $7$ Gesamtanzahl der möglichen Ergebnisse: $9 \cdot 8 \cdot 7$ |
Ziehen aller Kugeln ohne Zurücklegen mit Berücksichtigung der Reihenfolge |
Anzahl der möglichen Teilergebnisse: 1. Ziehung: $4$ 2. Ziehung: $3$ 3. Ziehung: $2$ 4. Ziehung: $1$ Gesamtanzahl der möglichen Ergebnisse: $4 \cdot 3 \cdot 2 \cdot 1$ |
Die Ergebnisse in der Übersicht lassen sich allgemein so beschreiben.
Urnenmodell: Ziehen mit Zurücklegen mit Berücksichtigung der Reihenfolge
Aus einer Urne mit $n$ durchnummerierten Kugeln wird $k$-mal eine Kugel mit Zurücklegen und mit Berücksichtigung der Reihenfolge gezogen. Für die Anzahl $N$ der verschiedenen Anordnungsmöglichkeiten gilt:
$N = {\underbrace{n \cdot n \cdot \ldots \cdot n}_{\text{k mal}}} = n^k$
Urnenmodell: Ziehen ohne Zurücklegen mit Berücksichtigung der Reihenfolge
Aus einer Urne mit $n$ durchnummerierten Kugeln wird $k$-mal eine Kugel ohne Zurücklegen und mit Berücksichtigung der Reihenfolge gezogen. Für die Anzahl $N$ der verschiedenen Anordnungsmöglichkeiten gilt:
$N = {\underbrace{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}_{\text{k mal}}}$
Urnenmodell: Ziehen aller Kugeln ohne Zurücklegen mit Berücksichtigung der Reihenfolge
Aus einer Urne mit $n$ durchnummerierten Kugeln wird $n$-mal eine Kugel ohne Zurücklegen und mit Berücksichtigung der Reihenfolge gezogen. Für die Anzahl $N$ der verschiedenen Permutationen der Kugelnummern gilt:
$N = n \cdot (n-1) \cdot \ldots \cdot 1$
Die Fakultätsschreibweise verwenden
Für Produkte der Gestalt $4 \cdot 3 \cdot 2 \cdot 1$ gibt es eine vereinfachte Schreibweise.
Mit $n!$ (gelesen: „n Fakultät“) wird das Produkt aller natürlichen Zahlen von $1$ bis $n$ beschrieben.
Beispiel:
$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$
Allgemein:
$n! = n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1$
Sonderfall:
$0! = 1$
Mit Hilfe der Fakultätsschreibweise lässt sich die Anzahl von Permutationen jetzt so formulieren.
Aus einer Urne mit $n$ durchnummerierten Kugeln wird $n$-mal eine Kugel ohne Zurücklegen und mit Berücksichtigung der Reihenfolge gezogen. Für die Anzahl $N$ der verschiedenen Permutationen der Kugelnummern gilt:
$N = n!$
Die folgende Umformung zeigt, dass auch Produkte der Gestalt $9 \cdot 8 \cdot 7$ mit Hilfe von Fakultäten beschrieben werden können:
$9 \cdot 8 \cdot 7 = \displaystyle{\frac{9 \cdot 8 \cdot 7 \quad \cdot \quad 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}} = \displaystyle{\frac{9!}{6!}} = \displaystyle{\frac{9!}{(9-3)!}}$
Hieraus ergibt sich die folgende alternative Beschreibung der Anzahl von Anordnungsmöglichkeiten:
Aus einer Urne mit $n$ durchnummerierten Kugeln wird $k$-mal eine Kugel ohne Zurücklegen und mit Berücksichtigung der Reihenfolge gezogen. Für die Anzahl $N$ der verschiedenen Anordnungsmöglichkeiten gilt:
$N = \displaystyle{\frac{n!}{(n-k)!}}$
Übersicht
Hier nochmal alle Ergebnisse in einer Übersicht:
Urnenziehung | Anzahl der Anordnungsmöglichkeiten |
---|---|
Ziehen mit Zurücklegen mit Berücksichtigung der Reihenfolge Beispiel: Allgemein: $k$-mal eine Kugel ziehen aus einer Urne mit $n$ durchnummerierten Kugeln |
Beispiel: $N = 5^3$ Allgemein: $N = n^k$ |
Ziehen ohne Zurücklegen mit Berücksichtigung der Reihenfolge Beispiel: Allgemein: $k$-mal eine Kugel ziehen aus einer Urne mit $n$ durchnummerierten Kugeln |
Beispiel: $N = 5 \cdot 4 \cdot 3$ Allgemein: $N = {\underbrace{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}_{\text{k mal}}}$ |
Ziehen aller Kugeln ohne Zurücklegen mit Berücksichtigung der Reihenfolge Beispiel: Allgemein: $n$-mal eine Kugel ziehen aus einer Urne mit $n$ durchnummerierten Kugeln |
Beispiel: $N = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5!$ Allgemein: $N = n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1 = n!$ |