Suche

Drucken Drucken

Kombinatorik

Die Kombinatorik beschäftigt sich damit, wie viele Möglichkeiten es gibt, verschiedene Objekte aus einer gegebenen Menge anzuordnen oder auszuwählen. Dabei gibt es Unterscheidungen zwischen
  • Dem mehrmaligen Ziehen eines Objektes:
    • Mit Zurücklegen: Ein Objekt kann mehrmals in der Liste auftauchen. Beispiel: Es wird mit einem Würfel mehrmals hintereinander gewürfelt. In mehreren Würfen kann die gleiche Augenzahl herauskommen.
    • Ohne Zurücklegen: Ein Objekt kann nur einmal in der Liste vorkommen. Beispiel: Aus einem Kartenspiel werden nacheinander Karten offen auf den Tisch ausgelegt. Eine bereits ausgelegte Karte kann nicht noch einmal gezogen werden.
  • Der Wichtigkeit der Reihenfolge
    • Reihenfolge ist wichtig; Variationen: Es ist wichtig, in welcher Reihenfolge die Objekte gezogen werden. So ist z.B. bei Spiel77 die Ziehung 1234567 eine andere als die Ziehung 1234576.
    • Reihenfolge ist unwichtig; Kombinationen: Es kommt z.B. beim Lotto nicht auf die Reihenfolge der gezogenen Zahlen an. Dies merkt man schon daran, dass die Lottozahlen der Größe geordnet wieder gegeben werden.

Permutation

Unter Permutation versteht man die Aufgabe, eine Anzahl von Objekten auf genau so viele Plätze zu platzieren. Dabei ist die Reihenfolge wichtig.
  • Permutation unterscheidbarer Objekte: Am Start eines Rennens stehen 6 Läufer. Wie viele Möglichkeiten gibt es, diese 6 Läufer auf die 6 Plätze, die sie erreichen, zu verteilen?
    Für den ersten Platz kommen 6 Läufer in Frage. Ist dieser Platz besetzt, gibt es noch 5 Möglichkeiten für Platz 2, dann wiederum 4 für Platz 3 und so weiter. Am Ende kommt man auf 6*5*4*3*2*1=720 Möglichkeiten. Oder allgemein: Es gibt n! Möglichkeiten, n Objekte auf n Plätze ohne Zurücklegen zu verteilen.
  • Permutationen mit Klassen von Objekten: Angenommen bei den sechs Läufern sind drei Läufer eines Vereins A dabei. Wie groß ist die Wahrscheinlichkeit, dass diese Läufer 3 Plätze direkt hintereinander belegen?
    Es gibt jetzt eigentlich nur noch vier Teilnehmer an dem Rennen: Die drei Läufer aus anderen Vereinen und der Block aus den Läufern des Vereins A. Damit gibt es erst einmal nach obiger Formel 4!=24 Möglichkeiten der Platzierung. Zusätzlich muss nun beachtet werden, dass die drei Läufer des Vereins A ihre Position untereinander auch tauschen können. Dafür gibt es 3!=6 Möglichkeiten. Also gibt es insgesamt 4!*3!=144 Möglichkeiten, dass die drei Läufer des Vereins hintereinander ins Ziel kommen.
  • Permutationen mit Wiederholungen: Es soll ermittelt werden, wie viele (mehr oder weniger sinnvolle) sechsbuchstabige Worte aus dem Wort Ananas gebildet werden können. Da man zwischen den 3 A und den 2 N nicht unterscheiden kann, werden es weniger als 6! Möglichkeiten sein. Es ergeben sich \frac{6!}{3!*2!*1!} Möglichkeiten. Allgemein: lassen sich die k Elemente in m Klassen mit k_1,k_2,...k_m \text{ und } k=\sum_{i=1}^mk_i Elementen unterteilen, so gibt es

        \[\frac{n!}{k_1!*k_2!*...*k_m!}\]

    Möglichkeiten.

Variation

Bei Variationen ist die Reihenfolge der Objekte wichtig. Es geht darum n Objekte auf k Plätze zu verteilen. Dabei muss unterschieden werden, ob Objekte zurückgelegt werden oder nicht.
  • Mit Zurücklegen: Beim Spiel 77 gibt es 10 Objekte und 7 Plätze. Dabei kann eine Zahl mehrmals in der Ziehung auftauchen. Es gibt n^k, in diesem Beispiel also 10^7, Möglichkeiten.
  • Ohne Zurücklegen: 8 Karten sollen auf 5 Plätze verteilt werden, wobei die Reihenfolge wichtig ist. Gezogene Karten werden offen ausgelegt und nicht in den Stapel zurück gelegt. Es gibt

        \[\binom{n}{k}*k!=\frac{n!}{(n-k)!}\]

    Möglichkeiten. Dabei ist \binom{n}{k} definiert als \frac{n!}{k!*(n-k)!}.

Kombination

 Bei Kombinationen ist die Reihenfolge der Objekte unwichtig. Es geht wieder darum, n Objekte auf k Plätze zu verteilen. Auch hier wird wieder unterschieden zwischen Ziehen mit und ohne Zurücklegen:

  • Mit Zurücklegen: Es wird mit zwei gleichen Würfeln gewürfelt n=6, k=2). Wie viele Ergebnisse gibt es? Da die Würfel gleich sind und gleichzeitig geworfen werden, spielt die Reihenfolge keine Rolle. Es gibt dann

        \[\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!*(n-1)!}\]

    Möglichkeiten. In diesem Beispiel:

        \frac{7!}{2!*5!}=21 \( verschiedene mögliche Ergebnisse.</li>  	<li>Ohne Zurücklegen: Beim Lotto werden 6 Zahlen aus 49 gezogen. Es gibt insgesamt <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://lernwerkstatt-selm.de/wp-content/ql-cache/quicklatex.com-99b592bd093b36bf3db40ee6fca58f14_l3.png" height="45" width="161" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[\binom{n}{k}=\frac{n!}{k!*(n-k)!}\]" title="Rendered by QuickLaTeX.com"/> Möglichkeiten. Hier: <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://lernwerkstatt-selm.de/wp-content/ql-cache/quicklatex.com-d3c69012de63c94a158d750739e732bf_l3.png" height="45" width="469" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[\binom{49}{6}=\frac{49!}{6!*43!}=\frac{49*48*47*46*45*44}{6*5*4*3*2*1}=13.983.816\]" title="Rendered by QuickLaTeX.com"/> Möglichkeiten{{1}}[[1]]Den Binomialkoeffizienten \(\binom{n}{k}

    kann man immer so ausrechnen, das man zwei Produkte dividiert. Das erste dieser Produkte besteht aus k Faktoren, beginnend mit n. Die folgenden Zahlen sind jeweils um 1 kleiner. Das zweite Produkt wird ähnlich gebildet; auch es besteht aus n Faktoren – beginnend mit k und die folgenden Zahlen werden ebenfalls jeweils um 1 vermindert.[[1]]. Den Ausdruck \binom{n}{k} nennt man auch Binomialkoeffizienten. Die einzelnen Werte kann man mit Hilfe des Pascalschen Dreiecks berechnen.

Der Unterschied zwischen Kombination und Variation

Um den Unterschied zwischen Variation (Beachtung der Reihenfolge) und Kombination (ohne Beachtung der Reihenfolge) zu verdeutlichen, betrachten wir folgende Situation:

  • Aus 49 Zahlen sollen sechs ohne Zurücklegen gezogen werden; allerdings soll es – anders als beim Lotto – auf die Reihenfolge ankommen. Mit anderen Worten: die Ziehung 1 – 2 – 3 – 4 – 5 – 6 ist eine andere als die Ziehung 6 – 5 – 4 – 3 – 2 – 1. Wie viele Möglichkeiten gibt es? Für den ersten Platz der Ziehung gibt es 49 Möglichkeiten, für den zweiten 48 usw., bis es für den sechsten Platz noch 44 Möglichkeiten gibt; insgesamt also

        \[49*48*47*46*45*44=10.068.347.520\]

    Möglichkeiten. Dies entspricht in der Formel \frac{n!}{(n-k)!}=\frac{49!}{43!}.

  • Um zu verdeutlichen, wie sich die Formel ändert, wenn die Reihenfolge keine Rolle bei der Ziehung spielt{{2}}[[2]]Dies bedeutet also, dass die Ziehungen 1 – 2 – 3 – 4 – 5 – 6 und 6 – 5 – 4 – 3 – 2 – 1 gleich sind.[[2]] überlegen wir uns, wie viele Möglichkeiten es gibt, sechs Zahlen auf sechs Plätze zu verteilen. Dies sind 6!=720 Möglichkeiten (Formel für Permutationen ohne Wiederholung). Dies bedeutet in unserem Beispiel, dass es 720 Möglichkeiten gibt, das Ziehungsergebnis 1 – 2 – 3 – 4 – 5 – 6 zu erzielen.
  • Im Fall der Lottoziehung werden aus 49 Zahlen 6 ohne Zurücklegen und ohne Beachtung der Reihenfolge gezogen. Das Ergebnis, dass wir im Fall der Beachtung der Reihenfolge erhalten haben (10.068.347.520 Möglichkeiten), muss durch 720 geteilt werden, weil es 720 Möglichkeiten gibt, dieses eine Ergebnis zu erzielen. Es ergeben sich damit 13.983.816 Möglichkeiten. Aus der Formel wird

        \[\binom{n}{k}=\frac{n!}{(n-k)!*k!}\]

    und damit in diesem Beispiel – nach Kürzen – \frac{49*48*47*46*45*44}{6*5*4*3*2*1}.

Die folgenden Tabelle fasst die Formeln aus diesem Text zusammen.

Mit Beachtung der Reihenfolge (Variation) Ohne Beachtung der Reihenfolge (Kombination) Permutation
Ohne Wiederholung \frac{n!}{(n-k)!} \binom{n}{k}=\frac{n!}{(n-k)!*k!} n!
Mit Wiederholung n^k \binom{n+k-1}{k}=\frac{(n+k-1)!}{k!*(n-1)!} \frac{n!}{k_1!*k_2!*...*k_m!}

Beispiele

Aufgabe 1: Kombination mit Gruppen

Wie groß ist die Wahrscheinlichkeit, 4 Richtige im Lotto zu haben?

Wir sind in einem Fall der Kombination (Reihenfolge spielt keine Rolle) ohne Zurücklegen. Es gibt insgesamt die oben bereits ausgerechnete \binom{49}{6} Möglichkeiten. Allerdings gibt es jetzt zwei Gruppen von Ergebnissen: Es gibt 6 richtige Zahlen – also die Zahlen, die wirklich gezogen werden – und 43 falsche. Unter den 6 richtigen befinden sich 4 von denen, die ich auf dem Tippschein habe. Die beiden anderen Zahlen, die ich getippt habe, sind unter den 43 Falschen. Damit ist die Wahrscheinlichkeit für 4 Richtige

    \[\frac{\binom{6}{4}*\binom{(43}{2}}{\binom{49}{6}}.\]

Aufgabe 2: Kombination mit Gruppen

 

Wie groß ist die Wahrscheinlichkeit, beim Lotto 6 aus 49 drei richtige Zahlen mit Zusatzzahl zu tippen?
Es gibt drei Gruppen von Zahlen. Auf unserem Schein sind drei richtige Zahlen, die Zusatzzahl und zwei falsche Zahlen:
  • richtige Zahlen: sechs, von denen wir drei brauchen
  • Zusatzzahl: eine, die wir brauchen und
  • falsche Zahlen: 42, von denen wir zwei brauchen.
Somit ergeben sich für drei richtige mit Zusatzzahl die Wahrscheinlichkeit

    \[\frac{\binom{6}{3}*\binom{1}{1}*\binom{42}{2}}{\binom{49}{6}}.\]

 

Aufgabe 3: Permutation

 

Wie viele Möglichkeiten gibt es, 8 Leute auf 8 Plätze an einem Tisch zufällig zu verteilen?
Wir sind bei einer Permutation (Es gibt gleich viele Objekte und Plätze!). Damit ist die Anzahl Möglichkeiten 8!=40.320.

 

Aufgabe 4: Permutation mit Gruppen

 

Wie sieht es aus, wenn 4 Paare eingeladen werden sollen und ein Paar jeweils nebeneinander sitzen soll?
Wir sind wieder bei Permutationen, allerdings haben wir es jetzt mit Unterklassen zu tun. Es gibt 4!*2!*2!*2!*2!=384 Möglichkeiten. Prinzipiell gibt es jetzt nur noch vier Teilnehmer (die 4 Paare), daher die 4!. Jedes der Paare hat aber zwei Möglichkeiten, sich auf seine beiden Plätze zu setzen, daher pro Paar 2! Möglichkeiten.

 

 

 

Drucken Drucken

Schreibe einen Kommentar