Oberstufe

W.12 | Kombinatorik

Eine Wahrscheinlichkeit muss fast immer mit irgendeiner Anzahl von Möglichkeiten, sprich Vertauschungen (=Kombinationsmöglichkeiten) multiplizieren. D.h., dass Vertauschungsmöglichkeiten sehr wichtig sind. Leider kann man nicht alle Kombinationsmöglichkeiten des Universums mit 2, 3 Formeln berechnen. Daher gibt es eine halbe Wissenschaft zu diesem Thema, die „Kombinatorik“.

 

W.12      Kombinatorik

Die Kombinatorik ist die Lehre von den Vertauschungsmöglichkeiten.
Da man eigentlich fast jede Wahrscheinlichkeit mit irgendwelchen Vertauschungsmöglichkeiten multiplizieren muss, ist es nahe­liegend, dass die Kombinatorik wichtig ist.
Es gibt recht viele Formeln in der Kombinatorik. Die meisten kann man in der Stochastik verwenden, muss sie aber nicht verwenden.
Die Standardtheorien der Kombinatorik müssen Sie beherrschen [Kapitel W.12.01]
Den Binomialkoeffizienten müssen Sie ebenfalls beherrschen [Kapitel W.12.02]
Den Multinomialkoeffizienten müssen Sie nicht beherrschen, manchmal ist er jedoch recht hilfreich [Kapitel W.12.03]

 

W.12.01 | Aufgaben zu Vertauschungsmöglichkeiten

Oftmals ist es sinnvoll, sich ein Ereignis in „Bestandteile“ zu zerlegen, sich also für jedes Einzelereignis zu überlegen, wieviel Möglichkeiten jeweils bestehen.


Beispiel a.

Sechs Personen sollen sich auf sechs Stühle setzen. Wieviele Möglichkeiten gibt es ?

Lösung:

Wir schauen uns jede Person einzeln an, d.h. wir überlegen uns, wieviel Sitzmöglichkeiten die erste Person hat, dann wieviel Sitzmöglichkeiten die zweite hat, dann die dritte, ....
Die erste Person hat 6 Stühle zur Auswahl, sie hat also 6 Möglichkeiten.
Bei der zweiten Person, gibt´s nur noch 5 freie Stühle, damit 5 Möglichkeiten
Die dritte Person hat dementsprechend noch 4 Möglichkeiten,  usw...

Wir malen uns also 6 gelbe Kästchen hin [für die 6 Personen] und schreiben in jedes Kästchen die Anzahl der Möglichkeiten rein, die diese Person hat.
⇒    Gesamtmöglichkeiten:   6  · 5  ·  4  ·  3  ·  2  ·  1   =  720 Möglichkeiten

 

Bemerkung:

„6·5·4·3·2·1“ kürzt man in Mathe mit „6!“ ab. (Aussprache: „sechs fakultät“)
Fakultäten werden Sie in der Wahrscheinlichkeits­rechnung öfter begegnen, das lohnt sich zu merken.

 

Beispiel b.

Sechs Personen sollen sich auf acht Stühle setzen. Wieviele Möglichkeiten gibt es ?

Lösung:
Wir betrachten eine Person nach der anderen und wieviel Möglichkeiten jede hat.
Die erste Person hat 8 Stühle zur Auswahl, die zweite noch 7, die dritte noch 6, …
⇒    Gesamtmöglichkeiten:   8  · 7  ·  6  ·  5  ·  4  ·  3   =  20160 Möglichkeiten

 

Beispiel c.

Acht Personen sollen sich auf sechs Stühle setzen. Zwei stehen Personen stehen; die Stühle stehen alle. Wieviele Möglichkeiten gibt es?

Lösung:
Wenn wir wieder von den Personen ausgehen, wird´s kompliziert.
Die erste Person hat zwar 6 Stühle, die zweite wieder 5 Stühle, … aber dummerweise bleiben 2 Personen übrig und dafür gibt es mehrere Möglichkeiten. Wir müssten dieses also noch mit berücksichtigen, die Aufgabe würde auf diesem Weg jedoch recht hässlich werden. Wir gehen statt dessen Aufgabe anders an.

Da es weniger Stühle als Personen gibt, betrachten wir die Aufgabe aus Sicht der Stühle: Auf den ersten Stuhl könnten sich acht Personen drauf setzen, auf den zweiten könnten sich noch sieben setzen, …
Damit haben wir [wie in Bsp.2]:    8  · 7  ·  6  ·  5  ·  4  ·  3   =  20160 Möglichkeiten

 

Beispiel d.

Acht Personen gehen in ein Haus mit sechs Räumen. Wieviele Möglichkeiten gibt es sich zu verteilen?

Lösung:

Gehen wir wieder von den Räumen aus: Im ersten Raum können sich 8 Personen befinden, im zweiten auch acht, ... Es gibt allerdings ein Problem: Es stimmt nicht unbedingt, dass im zweiten Raum acht Personen sein können, das hängt davon ab, wieviel bereits im ersten Raum sind. [Wenn im ersten Raum 6 Leute drin sind, können in allen anderen insgesamt nur noch 2 sein]. Wir bräuchten also eine ziemlich komplizierte Fallunterscheidung. Statt dessen probieren wir das Problem wieder von der anderen Seite aus zu betrachten.

Wir betrachten den Fall also von den Personen aus.

Die erste Person kann in 6 Räume gehen, egal in welchen Raum sie gehen, hat die zweite Person wieder 6 Räume zur Auswahl, die dritte auch ....

Es gibt also  6  · 6  ·  6  ·  6  ·  6  ·  6  ·  6  ·  6   =  68 Möglichkeiten

 

Moral von der Geschichte:  Es ist nicht immer klar, welche Methode man anwenden muss. Damit der Lösungsweg sinnvoll ist, man muss es ausprobieren.

 

Beispiel e.

Eine Münze wird 25mal geworfen.

a)    Wieviel Ausgangsmöglichkeiten gibt es?
b)    Wie viele Möglichkeiten gibt es, dass sich Kopf und Zahl abwechseln.

Lösung:
a)    Für jeden einzelnen Wurf gibt es zwei Ausgangsmöglichkeiten: Kopf oder Zahl.
    Bei 25 Würfen sind das also 2·2·2·2·... = 225 Möglichkeiten
b)    Es gibt zwei Möglichkeiten, dass sich Kopf und Zahl abwechseln:

K    Z   K    Z   K    Z   K    Z   K    Z....       oder:

Z   K    Z   K    Z   K    Z   K    Z   K....      >>>  25 Mal

 

 

 

 

 

 

W.12.02 | Binomialkoeffizient

Der Binomialkoeffizient ist sehr, sehr wichtig.

Es gibt zwei wichtige Anwendungsbereiche:
1.    Der Binomialkoeffizient liefert eine Anzahl von Vertauschungsmöglichkeiten. Bedingung ist, dass es nur zwei Ausgangsmöglichkeiten gibt [z.B. schwarze Kugeln und nichtschwarze Kugeln oder Kopf und Zahl beim Münzwurf...] und dass jede beliebige Reihenfolge der beiden Sorten erlaubt ist. Der Binomial­koeffizient ist eim wichtiger Bestandteil der Binomialverteilung [Kapitel W.16].
2.    Bei vielen Aufgaben zum Ziehen ohne Zurücklegen [vor allem bei den hässlichen Aufgaben] vereinfacht der Binomialkoeffizient die Rechnung ungemein. Diesen Fall behandeln wir in diesem Kapitel jedoch nicht, den finden Sie in Kapitel W.17 hypergeometrische Verteilung.

 

Der Binomialkoeffizient

berechnet Vertauschungs­möglichkeiten von 2 Gruppen.

Die Anzahl ist:

k1 = Anzahl von Gruppe 1,

k2 = Anzahl von Gruppe 2,

n = Gesamtanzahl ⇒ n=k1+k2

 

Nochmal zusammengefasst:

Der Binomialkoeffizient liefert eine Anzahl von Möglichkeiten, speziell die Anzahl von Vertauschungsmöglichkeiten von zwei Gruppen.
Man kann den Binomialkoeffizienten jedoch auch anwenden, wenn man aus einer großen Gruppe eine kleinere Anzahl auswählen soll!! [Denn damit hat man die große Gruppe wieder in zwei Untergruppen aufgeteilt: diejenige Untergruppe, die ausgesucht wurde – und diejenige Untergruppe, die nicht ausgesucht wurde]

Man berechnet die Anzahl immer mit:  
Dabei ist n immer die Gesamtanzahl der Elemente, k ist immer die Anzahl der Elemente von einer Untergruppe [egal von welcher der beiden].
Im Taschenrechner wird das eigentlich immer über den Befehl „nCr“ eingegeben.

Aussprache:

    nennt man entweder:  „k aus n“  oder  „n über k“

 

Den Binomialkoeffizienten wendet man an in den Fällen:

1. Es gibt zwei Gruppen von ununterscheidbaren Elementen.

Die Frage lautet: Wieviel Möglichkeiten gibt es, diese Elemente zu vertauschen?

(z.B. Wieviel Möglichkeiten gibt es 5 rote und 8 schwarze Kugeln einer Urne zu entnehmen?)

Siehe Beispiel f., oder siehe Kapitel W.16 Binomialverteilung

 

2. Aus einer großen Gruppe von unterscheidbaren Elementen will man eine kleinere Teilgruppe entnehmen.

Die Frage lautet: Wieviel Möglichkeiten gibt es für die Entnahme?

(z.B. Wieviel Möglichkeiten gibt es von 8 Touristen 3 Stück zu entführen?)

Siehe Beispiel h., oder siehe Kapitel W.17 hypergeometrische Verteilung

 

 

Beispiel e.

Wieviel Möglichkeiten gibt es 8 rote und 5 blaue Kugel in einer Reihe hintereinander aufzustellen?

Lösung:

Ganz einfach: 

 

 

Beispiel f.

Eine Münze wird zwanzig mal geworfen. Dabei werden die möglichen Ergebnisse Kopf (K) oder Zahl (Z) hintereinander notiert. Auf wieviel Arten kann das geschehen?

Lösung:
Falls Sie gerade an den Binomialkoeffizienten gedacht haben, wurden Sie gerade erfolgreich von mir veräppelt, die Frage kann nämlich nicht mit dem Binomialkoeffizienten beantwortet werden.
Warum? Es ist nicht klar aus wieviel Elementen die Untermengen (K und Z) bestehen. [Auf Deutsch: Es ist nicht klar wie oft K und wie oft Z geworfen wurden.]
Übrigens:  Da man bei jedem Wurf zwei Möglichkeiten hat,
lautet die richtige Lösung der Aufgabe: 2·2·2·2· ... = 220

 

 

Beispiel g.

Ganz böse Terroristen nehmen 8 unschuldige und liebe Touristen gefangen.
Nach einer Woche werden 3 Touristen freigelassen [oder erschossen, Sie können das von Ihrem momentanen Agressivitätszustand abhängig machen].
Wieviel Möglichkeiten gibt es dafür?

Lösung:
Aus der großen Gruppe der 8 Leute werden 3 ausgesucht...

 

 

Beispiel h.

Auf einem Stapel liegen liegen zwölf Herz-Karten und neun Pik-Karten.

Wieviel Möglicheiten gibt es, daraus sechs Karten zu ziehen?

Lösung:
Da nicht klar ist, aus wieviel Herz- bzw. Pik-Karten die Auswahl bestehen soll, ignorieren wie die Farben. Wir betrachten also den Fall: Aus einem Stapel mit 21 Karten werden sechs Stück entnommen. 

 

 

Beispiel i.

In einer Zoohandlung befinden sich zwölf weibliche und neun männliche Kanarienvögel. Karlchen möchte drei Pärchen davon kaufen. Wieviel Möglichkeiten hat er?

Lösung:

Nach heutigem Stand der Wissenschaft besteht ein Pärchen üblicherweise aus zwei verschiedenen Geschlechtern [die Ausnahmen, welche die Regel bestätigen, möchten wir hier ignorieren]. Die drei Pärchen setzen sich also drei Weibchen und drei Männchen zusammen. Nun haben wir also den Fall, dass wir aus zwölf vorhandenen Weibchen 3 Stück aussuchen müssen und aus neuen vorhandenen Männchen ebenfalls 3 Stück. Beide dieser Möglichkeiten berechnet man mit jeweils einem Binomialkoeffizient.

Das gibt 

 

 

Beispiel j.

In einer Zoohandlung befinden sich zwölf weibliche und neun männliche Kanarienvögel. Karlchen möchte drei Pärchen davon kaufen. Ein Weibchen ist so schön und anmutig, dass er es Rita Gierling nennt und auf jeden Fall dabei haben möchte. Wieviel Auswahlmöglichkeiten hat er nun?

Lösung:
Am einfachsten ist es wenn wir mit Rita anfangen. Wenn Rita dabei sein muss, stehen nur noch 11 Weibchen zur Verfügung, aus denen 2 ausgesucht werden sollen, aus den 9 Männchen müssen unverändert 3 ausgesucht werden.

Es gibt also: 

 

 

 

 

 

 

W.12.03 | Multinomialkoeffizient

Der Multinomialkoeffizient wird nicht sehr häufig verwendet, obwohl er eigentlich nicht besonders schwierig ist und sogar noch mehr Anwendungs­möglichkeiten als der Binomialkoeffizient hat.
Im Gegensatz zum  Binomialkoeffizient, der die Vertauschungsmöglichkeiten von zwei Gruppen angibt, kann man mit dem Multinomialkoeffizienten die Vertauschungsmöglichkeiten von beliebig vielen Gruppen berechnen.

 

Der Multinomialkoeffizient
berechnet Vertauschungs­möglichkeiten von mehreren Gruppen. Die Anzahl ist:

k1, k2, k3, … = Anzahl der

verschiedenen Gruppen

n = Gesamtanzahl

⇒ n=k1+k2+k3+...

 

 

 

Beispiel k.

In einer Urne befinden sich 5 rote, 7 gelbe und 4 weiße Kugeln. Wieviel Möglichkeiten gibt es, alle diese Kugeln der Urne zu entnehmen?

Lösung:

5 rote, 7 gelbe und 4 weiße Kugeln, die Gesamtanzahl ist 16.

 

 

Beispiel m.

Ein Glücksrad zeigt die Zahlen 1 bis 4. Die „1“ erscheint drei Mal, die „2“ erscheint nicht, die „3“ fünf Mal und die „4“ erscheint vier Mal.
Wieviel Möglichkeiten gibt es, die Zahlen anzuzeigen?

Lösung:
Die Häufigkeiten der Gruppen betragen: 3, 0, 5 und 4. Die Gesamtanzahl ist offensichtlich 12.