Kombinatorik und Stochastik


Online Rechner

Der Rechner von Simplexy kann dich beim Lösen vieler Aufgaben unterstützen. Bei einigen Aufgaben ist der Online Rechner mit Rechenweg auch in der Lage den Lösungsweg zu zeigen.



Kombinatorik

Die Kombinatorik beschäftigt sich damit, die Anzahl an möglichen Anordnungen bei einem Versuch zu bestimmen. Bei manchen Versuchen spielt die Reihenfolge der Ereignisse eine Rolle und bei anderen nicht, das hat Einfluss auf die Zahl der verschiedenen Kombinationen. Die Anzahl an Anordnungen wird auch davon beeinflusst, ob Wiederholungen (Zurücklegen) zugelassen werden oder nicht. Du wirst im Folgenden alles relevante über die Kombinatorik erklärt bekommen.




Stell dir eine Nachhilfegruppe mit drei Schülern und ein Lernraum mit drei Stühlen, die nebeneinander gestellt sind, vor. Die drei Schüler nennen wir sie Spongbob, Patrick und Sandy setzten sich in den Raum rein, dabei nehmen sie folgende Sitzordnung ein:

Spongbob \(\,\,\,\,\,\,\) Patrick \(\,\,\,\,\,\,\) Sandy

Am nächsten Tag setzen sie sich aber folgendermaßen hin:

Patrick \(\,\,\,\,\,\,\) Spongbob \(\,\,\,\,\,\,\) Sandy

Jeder dieser Sitzordnungen nennt man Permutation. Nun kann man sich fragen wie viele verschiedene Permutationen gibt es insgesamt. Schreiben wir sie mal alle Auf:


Platz 1 Platz 2 Platz 3
Spongbob Patrick Sandy
Spongbob Sandy Patrick
Patrick Spongbob Sandy
Patrick Sandy Spongbob
Sandy Patrick Spongbob
Sandy Spongbob Patrick

Es gibt also \(6\) verscheidene Permutation der Sitzordnung. In diesem Beispiel mit der Sitzordnung ist man in der lage alle Permutationen aufzuschreiben und nach zu zählen wie viele es insgesammt gibt. Wie geht man aber vor wenn man eine Klasse mit \(7\) Schülern hat. Wie ermittelt man für eine etwas größere Klasse die Anzahl an Permutationen der Sitzordnung, ohne sie alle aufschreiben zu müssen. Diese Fragen werden mit Hilfe der Kombinatorik beantwortet.


Allgemeines Zählprinzip

Betrachten wir nochmal das Beispiel mit der Sitzordnung von Spongebob, Patrick und Sandy. Wir fragen uns wie viele verschiedene Sitzordnung es gibt:

Nehmen wir an Spongbob kommt als erstes ins Zimmer und hat die freie Wahl sich irgendwo zu setzen.

Anschließend kommt Patrick in den Raum, da Spongbob bereits auf einem Stuhl sitzt sind nur noch zwei Plätze frei. Für Patrick sind also nur noch zwei Möglichkeiten sich auf einen Stuhl zu setzten.

Da Sandy zuletzt kommt, hat sie keine Wahl mehr als auf den übrigen freien Platz zu gehen.

Nach dem Zählprinzip ist die Anzahl an Möglichkeiten, eine Sitzordnung mit \(3\) Schülern aufzustellen gerade das Produkt aus den Möglichkeiten der einzelnen Schülern.

\(3\) Sitzmöglichkeiten von Spongbob mal \(2\) Sitzmöglichkeiten von Patrick mal \(1\) Sitzmöglichkeit von Sandy.

Somit gibt es \(3\cdot 2\cdot 1=6\) verschiedene Sitzordnungen.

Dafür kann man \(3!\) (\(3\)-Fakultät) schreiben.

Betrachten wir ein anderes Beispiel des Zählprinzips.

Thaddäus hat \(2\) Paar Schuhe, \(3\) Hosen und \(5\) T-Shirts. Wie oft muss er sich umziehen, wenn er alle Kombinationsmöglichkeiten anprobieren möchte?

Vorgehensweise

Zu jedem seiner \(2\) Paar Schuhe hat er \(3\) Möglichkeiten eine Hose anzuziehen. Damit gibt es
\(2\cdot 3=6\) Schuhe-Hosen-Kombinationen.

Zu jeder der \(6\) Schuhe-Hosen-Kombination kann Thaddäus \(5\) verschiedene T-Shirts anziehen. Er hat also insgesammt
\(6\cdot 5=30\) Schuhe-Hose-T-Shirt Kombinationen.

Regel:

Zählprinzip

Sind \(k\) Mengen \(M_1,M_2,...,M_k\), die je \(n_1,n_2,...,n_k\) Elemente besitzen gegeben, dann lassen sich insgesammt

\(n_1\cdot n_2\cdot ...\cdot n_k\)

verschiedene Kombinationen zusammenstellen.


Permutationen

Wir haben herausgefunden, dass bei der Sitzordnung von Spongbob, Patrick und Sindy es insgesammt \(6\) verschiedene Permutationen gibt. Das hätten wir auch berechnen können, indem wir \(3!\) ausrechnen, denn wir haben \(n=3\) Schüler.

\(3!=3\cdot 2 \cdot 1 = 6\)

Für eine Klasse mit \(7\) Schülern exisieren also \(7!\) verscheidene Permutationen der Sitzordnung. Mit dem Online-Rechner von Simplexy kannst du \(7!\) berechnen.
Hier kommst du zum Online Rechner.

\(7!=5040\)

Eine Schulklasse mit \(7\) Schülern hat also \(5040\) verschiedene Sitzordnungen. Es wäre ein sehr großer Aufwand die \(5040\) Permutationen per Hand aufzuschreiben und nachzuzählen

Bei den Permutationen unterscheidet man noch Fälle in denen die Reihenfolge der Elemente berücksichtigt werden und Fälle indenen die Reihenfolge der Elemente nicht von Bedeutung ist. Desweitern kann man aus der Grundmenge \(n\) nur eine bestimmte Teilmenge \(k\) permutieren. Zum Beispiel aus einer Schulklasse mit \(n=7\) Schülern, betrachtet man nur die \(k=4\) Jungs.


1. Permutation

  • \(k=n\,\,\) (Es werden alle Elemente betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt


2. Variation

  • \(k\lt n\,\,\) (Es wird nur eine Stichprobe betrachtet, also \(k\) Elemente der Grundmenge \(n\) werden betrachtet)
  • Reihenfolge der Elemente wird berücksichtigt


3. Kombination

  • \(k\lt n\,\,\) (Es wird nur eine Stichprobe betrachtet, also \(k\) Elemente der Grundmenge \(n\) werden betrachtet)
  • Reihenfolge der Elemente wird nicht berücksichtigt


Weiterhin gibt es bei Permutationen, Variationen und Kombinationen jeweils zwei Fälle zu unterscheiden:

  • Sind die Elemente unterscheidbar, so spricht man von
    \(\,\,\,\,\,\,\) Permutation/Variation/Kombination ohne Wiederholung.
  • Sind die Elemente nicht unterscheidbar, so spricht man von
    \(\,\,\,\,\,\,\,\)Permutation/Variation/Kombination mit Wiederholung.

1.1 Permutation ohne Wiederholung

Wir betrachten \(n\) unterscheidbare Objekte, die wir nebeneinander in einer Reihe mit \(n\) Plätzen aufstellen wollen. Für das aller erste Objekt gibt es \(n\) Platzierungsmöglichkeiten, wir können uns also frei entscheiden wo wir es hinstellen wollen. Für das zweite Objekt haben wir nur noch \((n-1)\) Platzierungsstellen. Denn das erste Objekt besetzt bereits ein Platz auf den wir das zweite Objekt nicht mehr stellen können. Für das dritte Objekt gibt es \(n-2\) freie Plätze
...
Wenn wir nur noch das letzte Objekt zu platzieren müssen, ist nur noch ein Platz frei.

Mit Hilfe des Zählprinzips können wir die Anzahl an Permutationen folgendermaßen schreiben:

\(n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 1=n!\)

Regel:

Permutation ohne Wiederholung

Eine Permutation ohne Wiederholung ist eine Anordnung von Elementen einer Menge, dabei muss folgendes gelten:

  • Die Elemente sind unterscheidbar.
  • Kein Element darf mehrmals verwendet werden.

Anzahl der Anordnungen für \(n\) Objekte berechnet sich über \(n!\) (n-Fakultät)

Ein Beispiel hierfür haben wir bereits gehabt, wir haben die Anzahl an Sitzordnungen für eine Klasse mit \(7\) Schülern berechnet. Die Sitzordnung für Schüler erfüllt die Bedingungen für eine Permutation ohne Wiederholung. Alle Schüler sind unterscheidbar und kein Schüler kann auf mehr als ein Platz sitzen (mehrmaliges verwenden der Elemente). Damit lässt sich die Anzahl an Permutationen über \(7!\) berechnen.

Weiteres Beispiel

In einer Urne befinden sich vier verschiedene Kugeln. Wie viele Möglichkeiten gibt es die Kugeln in einer Reihe anzuordnen?

Es gibt insgesammt \(4!=24\) verschiedene Anordnungen.


1.2 Permutation mit Wiederholung

Betrachten wir nun eine Menge mit \(n\) Elementen, von denen jedoch \(k\)-Elemente identisch sind. Um die Anzahl an verschiedenen Permutationen zu berechnen muss man beachten, dass die identischen Elemente vertauschbar sind. Denn zwei identische Elemente können ihre Plätze tauschen ohne dabei eine neue Anordnung zu generieren.

Die Anzahl der Anordnungen für \(n\) Elemente von denen \(k\)-Elemente identisch sind berechnet sich über:

\(\frac{n!}{k!}\)

Sind nicht nur eine sondern \(l\) Gruppen, mit je \(k_1, k_2,...,k_l\) identischen Elementen, dann lautet die Formel wie folgt:

\(\frac{n!}{k_{1}! \cdot k_{2}!\cdot ...\cdot k_{l}! }\)

Regel:

Permutation mit Wiederholung

Eine Permutation mit Wiederholung ist eine Anordnung von \(n\) Elementen einer Menge unter denen \(k\)-Elemente identisch sind.

Anzahl der Anordnungen für \(n\) Objekte berechnet sich über \(\frac{n!}{k!}\)

Beispiel

In einer Urne befinden sich \(5\) Kuglen, davon haben \(3\) Kugeln die gleiche Farbe. Wie viele verschiedene Anordnungen gibt es wenn man die Kuglen in der Urne in einer Reihe aufstellen möchte?

\(\frac{5!}{3!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1}=\frac{120}{6}\)\(=20\)

Es gibt \(20\) verschiedene Anordnungen die Kugeln in der Urne in einer Reihe aufzustellen.

Beispiel

In einer Urne befinden sich \(5\) Kugeln, davon sind \(3\) Kugeln weiß und \(2\) Kugeln schwarz. Wie viele Möglichkeiten gibt es die Kugeln in der Urne in eine Reihe zu stellen.

\(\frac{5!}{3!\cdot 2!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)\cdot (2\cdot 1)}\)\(=10\)

Es gibt \(10\) verschiedene Anordnungen.


2.1 Variation ohne Wiederholung

Wir betrachten \(n\) Elemente von denen \(k\)-Elemente ausgewählt werden, wobei jedes Element nur einmal ausgewählt werden kann. Die \(k\)-Elemente werden auf \(n\) Plätzen verteilt.

Für das erste ausgewählte Element gibt es \(n\) Platzierungsmöglichkeiten. Für das zweite Element gibt es \((n-1)\) Platzierungsmöglichkeiten. Für das dritte gibt es \((n-2)\)... und für das letzte Objekt verbleiben noch \((n-k+1)\) Platzierungsmöglichkeiten.

Die Anzahl an verschiedenen Anordnungen berechnt sich über:

\(n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-k+1)=\)\(\frac{n!}{(n-k)!}\)

Regel:

Variation ohne Wiederholung

Bei einer Variation ohne Wiederholung werden \(k\) aus \(n\) Elementen unter Berücksichtigung der Reihenfolge ausgewählt, wobei jedes Element nur einmal ausgewählt wird.

Anzahl der Anordnungen für \(k\)-Elemente aus einer Menge mit insgesammt \(n\) Elementen berechnet sich über:

\(\frac{n!}{(n-k)!}\)

Beispiel

Aus einer Urne mit \(6\) verschiedenen Kuglen sollen \(3\) Kugeln ohne Zurücklegen (ohne Wiederholung) und unter beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es die gezogenen Kugeln in einer Reihe aufzustellen?

\(\frac{6!}{(6-3)!}=\frac{6!}{3!}=120\)

Es gibt \(120\) verschiedene Möglichkeiten \(3\) aus \(5\) Kugeln ohne Zurücklegen mit Berücksichtigung der Reihenfolge in eine Reihe zu legen.


2.2 Variation mit Wiederholung

Wir betrachten \(n\) Elemente aus denen \(k\)-Elemente unter Beachtung der Reihenfolge gezogen werden, wobei Elemente auch mehrfach ausgewählt werden können.

Für das erste gezogene Element gibt es \(n\) Auswahlmöglichkeiten. Da man Elemente mehrfach auswählen kann, gibt es für das zweite, dritte und k-te Element auch \(n\) Auswahlmöglichkeiten. Demnach berechnet sich die anzahl an Möglichkeiten über:

\(n\cdot n\cdot ...\cdot n=n^k\)

Regel:

Variation mit Wiederholung

Bei einer Variation mit Wiederholung werden \(k\) aus \(n\) Elementen unter Berücksichtigung der Reihenfolge ausgewählt, wobei jedes Element mehrfach ausgewählt werden kann.

Anzahl der Möglichkeiten für \(k\)-Elemente aus einer Menge mit insgesammt \(n\) Elementen berechnet sich über:

\(n^k\)

Beispiel

In einer Urne befinden sich \(6\) verschiedene Kugeln. Es sollen \(3\) Kugeln mit Zurücklegen (mit Wiederholung) und unter Beachtung der Reihenfolge gezogen werden. Wie viele verschiedene Möglichkeiten für die Reihenfolge mit der die Kugeln gezogen werden gibt es.

\(6^3=216\)

Es gibt \(216\) verschiedene Möglichkeiten für die Reihenfolge mit denen \(3\) Kugeln aus der Urne gezogen werden können.


3.1 Kombination ohne Wiederholung

Bei einer Kombination ohne Wiederholung werden aus \(n\) Elementen \(k\)-Elemente ohne Berücksichtigung der Reihenfolge ausgewählt. Dabei darf jedes Element nur einmal ausgewählt werden.

Die Variation ohne Wiederholung und die Kombinaion ohne Wiederholung unterscheiden sich also nur darin, ob die Reihenfolge der Elemente eine Rolle spielt oder nicht.

Wir wissen bereits wie man die Anzahl an Anordnungen für eine Variation ohne Wiederholung berechnet:


\(\frac{n!}{(n-k)!}\)


Bei der Kombination ohne Wiederholungen können die \(k\) ausgewählten Elemente auf \(k!\) verschiedene Weise angeordet werden, da ihre Reihenfolge nicht von Bedeutung ist, lautet die Formel demnach:


\(\frac{n!}{(n-k)!\cdot k!}=\binom{n}{k}\)

Den Term \(\binom{n}{k}\) nennt man Binomialkoeffizient, gesprochen sagt man \(n\) über \(k\).

Regel:

Kombination ohne Wiederholung

Bei einer Kombination ohne Wiederholung werden \(k\) aus \(n\) Elementen unter Vernachlässigung der Reihenfolge ausgewählt, wobei jedes Element nur einmal ausgewählt werden darf.

Anzahl der Möglichkeiten für \(k\)-Elemente aus einer Menge mit insgesammt \(n\) Elementen berechnet sich über:

\(\frac{n!}{(n-k)!\cdot k!}=\binom{n}{k}\)

Beispiel

In einer Urne befinden sich \(6\) verschiedene Kugeln. Drei Kugeln sollen nacheinander gezogen werden ohne dass sie wieder in die Urne gelegt werden. Die Reihnfolge der gezogenen Kugeln soll nicht von Bedeutung sein. Wie viele Möglichkeiten gibt es?

\(\binom{6}{3}=\frac{6!}{(6-3)!\cdot 3!}\)\(=20\)

Es gibt insgesamt \(20\) Möglichkeiten.


3.2 Kombination mit Wiederholung

Der unterschied zwischen der Kombination mit Wiederholung und der Kombination ohne Wiederholung liegt darin, dass bei der Kombination mit Wiederholung die Elemente mehrfach ausgewählt werden können.

Für die Kombination mit Wiederholung berechnet man die Anzahl an Anordnungen folgendermaßen:

\(\frac{(n-1+k)!}{(n-1)!\cdot k!}=\binom{n-1+k}{k}\)

Regel:

Kombination mit Wiederholung

Bei einer Kombination mit Wiederholung werden \(k\) aus \(n\) Elementen unter vernachlässigung der Reihenfolge ausgewählt, wobei jedes Element mehrmals ausgewählt werden darf.

Anzahl der Möglichkeiten für \(k\)-Elemente aus einer Menge mit insgesammt \(n\) Elementen berechnet sich über:

\(\frac{(n-1+k)!}{(n-1)!\cdot k!}=\binom{n-1+k}{k}\)

Beispiel

In einer Urne befinden sich \(6\) verschiedene Kugeln. Es werden \(3\) Kugeln gezogen nach jedem Zug wird die gezogene Kugel zurück gelegt. Die Reihenfolge wird nicht berücksichtigt.
Wie viele Möglichkeiten gibt es für die Reihenfolge mit der die Kugeln gezogen werden?

\(\binom{6-1+3}{3}=\binom{8}{3}=56\)

Es gibt insgesamt \(56\) Möglichkeiten.